Practice: Maximum Subarray
Kadane's algorithm.
A shop's daily profit goes up and down, sometimes negative. Find the stretch of days in a row with the biggest total profit. Pause. Is there a way to do it in one pass?

- Daily profit, ups and downs
- The best stretch of days
- One pass?
Kadane's algorithm
As we walk along, we keep the best total for a stretch ending today. Each day, we either add today to the stretch so far, or start fresh from today, whichever is bigger. If the stretch so far is negative, it only drags us down, so starting fresh wins. We also track the best we've ever seen. Run it. The best stretch makes six.
def max_subarray(nums):
current = best = nums[0]
for n in nums[1:]:
current = max(n, current + n)
best = max(best, current)
return best
profits = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(profits))6
Why Kadane's works
At every day, the best stretch ending there either includes yesterday's best stretch, or it doesn't. That's a tiny dynamic programming problem, solved with one variable. It's O of N time, and O of one space, compared with O of N squared for checking every stretch.
| key | value |
|---|---|
| Each day | extend, or restart |
| Restart when | the run is negative |
| Track | the best ever |
| Cost | O(n), O(1) space |
Summary
Kadane's algorithm extends the current stretch, or restarts it, and tracks the best total. One pass, O of N. Next, products without division.
Key takeaways- max(n, current + n)
- Track the best
- O(n)