A machine emits an energy reading (which may be negative) at each of n consecutive time steps. You want to pick a non-empty contiguous window of time steps so that the total energy inside the window is as large as possible.
Return that maximum total. Because the window must be non-empty, if every reading is negative the answer is the single largest (least negative) reading.
Input format
Line 1: an integer n, the number of readings.
Line 2: n space-separated integers, the readings (present whenever n >= 1).
Output format
A single integer: the maximum sum over all non-empty contiguous windows.
Constraints
- 1 <= n <= 100000
- -1000000 <= each reading <= 1000000
- The window must contain at least one element.