The problem
Find the contiguous block of numbers with the largest sum, and return that sum.
Input: [−2, 1, −3, 4, −1, 2, 1, −5, 4] Output: 6 ([4, −1, 2, 1])
Picture it
Picture a trading diary: each day shows a profit or a loss. We look for the best winning streak of consecutive days. Walking day by day, we carry the running total of the current streak. If that running total ever drops below zero, it can only hurt whatever comes next, so we drop it and start a fresh streak today.
How to recognise it
- You want the best contiguous block by sum (a subarray, so no gaps), and numbers can be negative.
- A running total that has gone negative can only hurt whatever comes next, so the greedy move is to drop it and start fresh.
- With up to 10^5 numbers, checking every start and end is too slow; one pass is expected.
- "Best block ending here" depends only on "best block ending at the previous position", which is why one running value is enough.
Start with brute force
Try every start, extend the end one number at a time with a running sum, and keep the largest sum seen.
def max_subarray_brute(days):
best = days[0]
for i in range(len(days)):
total = 0
for j in range(i, len(days)):
total += days[j]
best = max(best, total)
return best
There are about n²/2 blocks, so time is O(n²): for n = 10^5 that is about 5 × 10^9 additions, far too slow. Space is O(1).
From brute force to the idea
- Find the waste. The brute force re-adds long stretches that overlap with the previous start.
- Fix the end, vary the start. The best block that ends at position i is either the number alone, or the best block ending at i − 1 with this number added.
- Choose greedily.
cur = max(x, cur + x): if the running sumcuris negative,cur + xis smaller than x, so you restart at x. A negative prefix never helps a block extend. - Remember the best so far.
best = max(best, cur). The block need not end at the last position, sobestrecords the peak. - Seed with the first number. Starting both at
days[0]handles all-negative input correctly.
This is the key idea (Kadane's algorithm): keep the best sum ending here, restarting whenever the running sum would be worse than starting fresh.
The key idea
Kadane: cur = max(x, cur + x); best = max(best, cur). O(n).
Python solution
def max_subarray(days):
cur = best = days[0]
for x in days[1:]:
cur = max(x, cur + x) # keep the streak or start fresh
best = max(best, cur)
return bestIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): every start with every end | O(1): a running sum |
| Kadane (shown code) | O(n): one pass with two max calls per number | O(1): two variables |
Edge cases
- One number (
[5]): returns5; the loop does not run. - All negative (
[-3, -1, -2]): returns-1, the largest single number. The block must contain at least one number. - All positive: returns the sum of everything.
- Zero alone (
[0]): returns0. - Example
[-2, 1, -3, 4, -1, 2, 1, -5, 4]: returns6(the block 4, −1, 2, 1). - Restart after a dip (
[5, -3, 5]): returns7, since the dip of −3 does not make the running sum negative. - Empty list: raises
IndexErrorbecause ofdays[0]; the problem guarantees at least one number.
Common mistakes
- Starting
curandbestat 0, so[-1]returns 0 (an empty block, which is not allowed). - Returning
curinstead ofbest, which gives the sum of the block ending at the last position only. - Resetting the running sum to 0 whenever it is negative and then adding the next number, with
bestalso starting at 0. It works for mixed input but returns 0 for all-negative input. - Restarting at every negative number. The block restarts only when the sum so far is below 0, so a small dip inside a good run is kept.
The array is now circular: a block may wrap from the end back to the start. Return the largest sum of a non-empty block. For [5, -3, 5] the answer is 10 (5 + 5 wrapping round). Describe your approach, then write it if you like.
Compare with our answer
A wrapping block is the whole array minus a non-wrapping block, and the part left out should be as small as possible. So compute Kadane's maximum and Kadane's minimum, and compare the two options.
def max_circular(nums):
best_max = cur_max = nums[0]
best_min = cur_min = nums[0]
for x in nums[1:]:
cur_max = max(x, cur_max + x)
best_max = max(best_max, cur_max)
cur_min = min(x, cur_min + x)
best_min = min(best_min, cur_min)
if best_max < 0: # every number is negative
return best_max
return max(best_max, sum(nums) - best_min)
max_circular([5, -3, 5]) is 10 and max_circular([-3, -1, -2]) is -1. Time O(n), space O(1).
A strong answer mentions: the answer is the larger of the ordinary maximum and total minus the minimum block, the special case when every number is negative (total minus minimum would be an empty block), and that it is still a single pass.
1. You must find the contiguous stretch of days with the best total profit in a list of 100,000 daily results, some of them negative. Which approach fits best?
Today's best block is either today alone or yesterday's best block extended, so one pass is O(n). Sorting loses contiguity, subtracting the worst day removes one number rather than a prefix, and two loops are about 5 × 10^9 steps.
2. Why is the shown code O(n) time and O(1) space?
cur and best are all the state needed, and each number is processed once. Negative numbers are not skipped (they may lie inside the best block), and nothing is stored or sorted.
3. A learner starts with cur = best = 0 instead of days[0] and loops over every number. For which input is the answer now wrong?
With all negative numbers the learner's version never beats 0, so it returns 0 (an empty block) instead of −1. The other inputs contain a positive block, so their answers (3, 5 and 3) stay correct.
Score 60% or more and the lesson is marked complete.