LeetCode 53 · Greedy

Maximum Subarray (Kadane), explained with a picture

The best winning streak in a trading diary.

MediumGreedy
▶ Watch it step by step

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

  1. Find the waste. The brute force re-adds long stretches that overlap with the previous start.
  2. 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.
  3. Choose greedily. cur = max(x, cur + x): if the running sum cur is negative, cur + x is smaller than x, so you restart at x. A negative prefix never helps a block extend.
  4. Remember the best so far. best = max(best, cur). The block need not end at the last position, so best records the peak.
  5. 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 best

In 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

ApproachTimeSpace
Brute forceO(n²): every start with every endO(1): a running sum
Kadane (shown code)O(n): one pass with two max calls per numberO(1): two variables

Edge cases

  • One number ([5]): returns 5; 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]): returns 0.
  • Example [-2, 1, -3, 4, -1, 2, 1, -5, 4]: returns 6 (the block 4, −1, 2, 1).
  • Restart after a dip ([5, -3, 5]): returns 7, since the dip of −3 does not make the running sum negative.
  • Empty list: raises IndexError because of days[0]; the problem guarantees at least one number.

Common mistakes

  • Starting cur and best at 0, so [-1] returns 0 (an empty block, which is not allowed).
  • Returning cur instead of best, 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 best also 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.
Your turn: a circular array

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.

Check what stuck

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?

2. Why is the shown code O(n) time and O(1) space?

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?

Score 60% or more and the lesson is marked complete.