Question
The Enchanted Valley’s Darkest Segment
In a mysterious valley, a traveler walks along a path filled with enchanted stones. Each stone has an energy value, which can either heal (positive) or harm (negative) the traveler.
As the traveler walks, the total effect is determined by the sum of consecutive stones he steps on. Some segments may be extremely dangerous due to large negative energy.
Your task is to help the traveler find the most dangerous segment — that is, the contiguous subarray whose total energy is minimum possible.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of stones.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — representing the energy of each stone.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression — representing the energy of each stone.
Output
Print a single integer — the minimum possible sum of any contiguous subarray.
Example
Input
6
3 -4 2 -3 -1 7
Output
-6
Explanation
The most dangerous segment is:
KaTeX can only parse string typed expression
No other contiguous subarray has a smaller sum.
6
3 -4 2 -3 -1 7
Output
-6
Explanation
The most dangerous segment is:
KaTeX can only parse string typed expression
No other contiguous subarray has a smaller sum.