A tide gauge records n consecutive net-change readings, one per interval; each reading is the signed change in water level during that interval (it may be negative). A contiguous run of intervals accumulates the sum of its readings. Find the largest total accumulated by any non-empty contiguous run.
Line 1: an integer n.
Line 2: n space-separated integers, the readings in time order.
A single integer: the maximum sum achievable by a non-empty contiguous run.
Example 1
Input
9 -2 1 -3 4 -1 2 1 -5 4
Expected
6
Explanation
The run 4, -1, 2, 1 sums to 6, which is the largest achievable.
Example 2
Input
3 -5 -2 -8
Expected
-2
Explanation
Every reading is negative, so the best non-empty run is the single reading -2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →