Maximum Subarray
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Find the largest sum of any non-empty continuous sub-list.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Define "best streak that ends today". How is it built from yesterday's best streak?
- Hint 2When is it better to drop the old streak and start fresh?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A shopkeeper writes the profit or loss of each day. He wants the best stretch of days in a row. He carries a "current streak" in his head: if the streak so far is losing money it only drags him down, so he forgets it and starts fresh today. If it is positive he keeps adding today's number to it. He also remembers the best streak he has ever had.
- The obvious way
Try all start/end pairs with a running sum: O(n²).
- The key insight
For each day the best streak ending today is either today alone, or today added to the best streak ending yesterday, whichever is bigger. A negative old streak never helps, so it is dropped. Keep the biggest streak value seen on any day.
- The algorithm
- Current streak = first number; best ever = first number.
- For each next number: current streak = bigger of (the number alone, streak + the number).
- Best ever = bigger of (best ever, current streak).
- Return the best ever.
Watch it run
Exampledays = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Day 1: -2. Streak -2, best -2.
streak -2, best -2
Where people slip
- Do not start best at 0: an all-negative list must return the largest (least negative) number.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def max_sub_array(nums):
streak = best = nums[0]
for number in nums[1:]:
streak = max(number, streak + number) # extend, or start fresh
best = max(best, streak)
return bestNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.