AI Hints
Home›DSA in Python Tutorial›Array Interview Problems
DSA in Python · Lesson 106 of 132

Practice: Maximum Subarray

Kadane's algorithm.

⏱ 2 min read▶ Video at 2:06:52🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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?

Practice: Maximum Subarray
From the video: Practice: Maximum Subarray
  • 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.

kadane.pypython
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))
Output
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.

keyvalue
Each dayextend, or restart
Restart whenthe run is negative
Trackthe best ever
CostO(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)
Next up: Practice: Product Except Self — left and right passes