Given an integer array nums, find the contiguous, non-empty stretch of it whose numbers add up to the most, and return that sum.
[2,3,-1,5] adds up to 9. Taking the -1 is worth it because the 5 after it more than pays it back.
Every number is negative, so the best stretch is the single largest one. An empty stretch is not allowed.
Constraints
1 <= nums.length <= 10⁵-10⁴ <= nums[i] <= 10⁴Going further: after the O(n) approach, try a divide-and-conquer one.
Walk the array keeping the best sum of a subarray that ends at the current index.
Walk the array from left to right, and at each index i ask a narrower question than the problem does: what is the best sum of a stretch that ends exactly at i? The answer to the whole problem is the largest of these, since every stretch ends somewhere.
Time O(n)Space O(1)
The full walkthrough and code are part of Premium
9