Why it works
- The best run that ends at index i is nums[i] alone or nums[i] added to the best run that ends at i - 1. Nothing else can end there, so one number, here, carries all that matters from the left.
- A run behind with a negative sum only lowers whatever follows it, so the run starts fresh. With a sum of 0 or more it never hurts, so the run grows.
- Every run ends somewhere, so the largest here over all indices, kept in best, is the answer. best starts at nums[0], not 0, so an array of only negative numbers still gets its largest number.
Complexity
Time O(n): one pass, a constant amount of work per number. Memory O(1): only here and best; the rows in the picture are there to show their history.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗