A cricket club tracks the change in its membership each day (positive for joins, negative for leavers). Find the largest total of any run of consecutive days. The run must contain at least one day.
Constraints
- 1 ≤ n ≤ 100000
- −10000 ≤ value ≤ 10000
Input and output
- Input
- The first line has n. The second line has n integers.
- Output
- One integer: the largest sum of a non-empty contiguous run.
Examples
Input 1
6
-3 4 -1 2 -6 5Output
5The run 4, −1, 2 adds up to 5; so does the single day 5.
Input 2
3
-8 -2 -5Output
-2Every day is a loss, so the best run is the single smallest loss: −2.
Show hints
- If the run ending yesterday has a negative total, would you ever extend it?
- Track the best run that ends today.
Show the explanation
This is Kadane's algorithm. Let cur be the best total of a run ending at today. Either today extends yesterday's run or starts a new one, so cur = max(x, cur + x). The answer is the largest cur seen.
Starting cur and best from the first value (not 0) handles the case where every value is negative.
Original UniCircle question. Last reviewed 22 Oct 2026.