Maximum subarray sum
Extending a run only helps if it's still positive overall; otherwise start fresh from here. About 10 minutes.
The best streak ending today
Think of a trader's daily profits and losses: −2, 1, −3, 4, −1, 2, 1, −5, 4. Which run of consecutive days made the most money?
Walk through the days and keep one question in mind: what's the best streak that ends today? Either today joins yesterday's streak, or today starts a brand-new one on its own. If the streak you're carrying is already negative, it only drags today down, so drop it and start fresh.
- cur
- -2
- best
- -2
The only run ending here is [-2].
Keep the best you've ever seen
The best streak ending today goes up and down as you walk: a bad day can wreck it. So keep a second number: the best streak you've seen anywhere so far. It only ever goes up.
In the example, the streak 4, −1, 2, 1 reaches 6. The −5 afterwards pulls the current streak down, but the record stays at 6, and that's the answer.
here = best = nums[0]
for x in nums[1:]:
here = max(x, here + x)
best = max(best, here)
return bestDaily results are −2, 3, −1, 5. What's the best streak ending on the last day (the 5)?
- A7
- B5
Show the answer
7. The streak before it (3, −1) is worth 2, which is positive, so the 5 joins it: 3 − 1 + 5 = 7.
Maximum subarray sum
Given an array nums of at least one integer (it may include negative numbers), return the largest possible sum of any contiguous, non-empty run of nums.
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6
1 ≤ nums.length ≤ 100,000 · -1,000 ≤ nums[i] ≤ 1,000