Why it works
- The best run either stays inside the array, and plain Kadane finds it as hi, or it goes past the end. Then the numbers it leaves out form a run in the middle, and to make the kept part largest that left-out run must be the smallest: total - lo.
- The smallest run is found the same way as the largest, with min instead of max, in the same pass.
- If every number is negative, the smallest run is the whole ring and total - lo = 0 stands for taking nothing, which is not allowed. Then hi, the largest single number, is returned instead.
Complexity
Time O(n): one pass, each number updates five values. Memory O(1): five numbers; the rows in the picture show their history.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗