458. The Best Run Around a Circle
The array is CIRCULAR, so a run may wrap from the end back to the start. Print the largest sum of any non-empty run. A run may not use the same element twice.
5 -3 5 -> 10 the run 5, then wrapping to 5
1 -2 3 -2 -> 3
Problem #57 solves the straight version with one running value. Wrapping breaks it, because a wrapped run is not contiguous in the array as stored.
Duplicating the array and scanning 2n elements works but must then forbid runs
longer than n, which needs a window and is easy to get wrong.
The neat argument: a best run either wraps or it does not.
does not wrap -> the ordinary answer on the array
does wrap -> its complement is a NON-wrapping run, and the complement
is the minimum-sum run, so the answer is total - minimum
So compute the maximum run and the minimum run in one pass each, and take the better
of maximum and total - minimum.
One case breaks that and must be handled: if every element is negative, the
minimum-sum run is the WHOLE array, its complement is empty, and total - minimum
is 0, which no non-empty run achieves. So when the maximum run is itself negative,
the answer is that maximum.
-3 -2 -3 is in the tests for exactly this, answering -2 rather than 0.
Constraints - `1 ≤ n ≤ 200000` - `-10000 ≤ value ≤ 10000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print the largest sum of any non-empty run, allowing it to wrap around the end.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.