Best Streak Sum
Problem
A shop logs its net result for each day in changes (positive for a gain, negative for a loss). A streak is a run of one or more consecutive days.
Return the largest total of any streak. The streak must contain at least one day, even if every day was a loss.
Example 1
- Input:
- changes = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
- Output:
- 6
Days 3 to 6: 4 - 1 + 2 + 1 = 6.
Example 2
- Input:
- changes = [-3, -1, -2]
- Output:
- -1
Every day is a loss, so the best streak is the single day with -1.
Constraints
- 1 ≤ changes.length ≤ 10^5
- -10^4 ≤ changes[i] ≤ 10^4
Hint
Show the first hint
Fix the day where the streak ends. What is the best streak ending exactly there?
Walkthrough
How to approach it
01Clarify before coding
- Must the streak be non-empty? Yes, so with all losses the answer is the least negative day, not 0.
- Contiguous days only? Yes, a streak cannot skip days.
- Do I return the sum or the range? Just the sum.
02Brute force
Try every start day, extend to every end day keeping a running sum, and track the maximum.
Cost: O(n²) time, O(1) space: 5·10^9 additions for n = 10^5, far too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.