Maximum subarray: Kadane's algorithm

The problem

A subarray is a run of one or more neighbouring items. Given numbers that can be positive or negative, find the largest possible sum of a subarray. For [−2, 1, −3, 4, −1, 2, 1, −5, 4] the answer is 6, from the run [4, −1, 2, 1]. This shows up whenever you want the best stretch of time: the best run of days for a shop, or the strongest period of a signal.

Brute force: try every run

Pick every start l and every end r and add up nums[l..r]. Done naively that is O(n³); keeping a running sum while r moves makes it O(n²). Correct, but too slow for n = 10⁵.

def max_sub_brute(nums):
    best = nums[0]
    for l in range(len(nums)):
        running = 0
        for r in range(l, len(nums)):
            running += nums[r]
            best = max(best, running)
    return best

print(max_sub_brute([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # Output: 6

The key idea: best sum ending here

Every subarray ends somewhere. So ask a smaller question for each index i: what is the best sum of a run that ends exactly at i? Call it cur. Such a run either is just nums[i] on its own, or it is the best run ending at i − 1 with nums[i] added. So cur = max(nums[i], cur + nums[i]). In words: if the run so far has a negative sum, drop it and start fresh, because it can only drag the total down.

The answer is the largest cur seen at any index. This is Kadane's algorithm: O(n) time and O(1) space. It is also your first taste of dynamic programming (Module 11): solve a small question for each position and build on the previous answer.

def max_subarray_sum(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # Output: 6
print(max_subarray_sum([-3, -1, -2]))                      # Output: -1

All-negative arrays

If every number is negative, the best non-empty subarray is the single largest number, for example −1 in [−3, −1, −2]. A common buggy version starts best at 0 and returns 0, which is the sum of an EMPTY subarray. Ask the interviewer whether an empty subarray is allowed; usually it is not.

Returning the start and end

To report where the best run is, remember the index where the current run started. When you start fresh at i, set start = i. When cur beats best, save best_start = start and best_end = i. Decide a tie rule and state it. With "start fresh only when the previous run is negative" and "update best only when strictly greater", you get the run that ends earliest, and among those the longest one.

Cousin: buy and sell a stock once

Given daily prices, buy on one day and sell on a later day for the largest profit (or 0 if no profit is possible). Walk once, keep the lowest price so far, and at each day check price − lowest. O(n) time, O(1) space. It is the same idea: the best profit selling today depends only on the cheapest day before today. In fact it equals the maximum subarray of the day-to-day price changes.

def max_profit(prices):
    lowest = float("inf")
    best = 0
    for p in prices:
        lowest = min(lowest, p)
        best = max(best, p - lowest)
    return best

print(max_profit([7, 1, 5, 3, 6, 4]))   # Output: 5  (buy at 1, sell at 6)
print(max_profit([7, 6, 4, 3, 1]))      # Output: 0  (prices only fall)

Common mistakes

• Starting best at 0: wrong for all-negative input. Fix: start with nums[0].
• Resetting cur to 0 instead of to the current number. Fix: cur = max(x, cur + x).
• Forgetting the empty list. Fix: decide what to return (0, None or an error) and handle it first.
• In the stock problem, selling before buying, for example taking max(prices) − min(prices). Fix: only compare with the lowest price BEFORE the current day.
• Not stating a tie rule when returning indexes. Fix: say it, then make the comparisons (> or >=) match it.