Maximum Subarray Sum, in depth: Kadane's algorithm, prefix sums, a correctness proof, divide and conquer, and circular, product and 2D variants

The problem and the brute force

Input: an array a of n numbers, possibly negative. Output: the maximum of a[l] + ... + a[r] over all 0 <= l <= r < n, usually with the indices l and r. The subarray must be non-empty; that convention matters, and we return to it below.

Brute force enumerates every pair (l, r) and sums the elements between them: O(n^3). Keeping a running sum as r advances for a fixed l removes the inner loop: O(n^2). For n = 100,000 the quadratic version does five billion additions; the linear versions below do one hundred thousand.

A linear solution with prefix sums

Define prefix sums P[0] = 0 and P[k] = a[0] + ... + a[k-1]. The sum of a[l..r] is P[r+1] - P[l]. Maximising it for a fixed right end means subtracting the smallest prefix seen so far. One pass that tracks the running minimum prefix solves the problem in O(n) time and O(1) extra space:

def max_subarray_prefix(a):
    best = float("-inf")
    prefix, min_prefix = 0, 0          # P[0] = 0 is a legal left boundary
    for x in a:
        prefix += x
        best = max(best, prefix - min_prefix)
        min_prefix = min(min_prefix, prefix)
    return best

Note the order: the candidate is computed before the minimum is updated, so the subarray can never be empty. This view is also the one that generalises to constraints such as "length at least k": keep the minimum over prefixes ending at least k positions back.

Kadane&#x27;s recurrence

Kadane's algorithm reaches the same bound with a dynamic-programming argument. Let cur(i) be the best sum of a subarray that ends exactly at i. Such a subarray either is a[i] alone or extends the best subarray ending at i-1:

cur(i) = max(a[i], cur(i-1) + a[i]), and the answer is the maximum of cur(i) over all i.

Read the recurrence in words: if the best run ending at the previous position has a negative sum, it can only drag a[i] down, so start fresh at i; otherwise extend it. Each cur(i) depends only on cur(i-1), so the table collapses to one variable. The same "best ending here" state appears in the house robber state machine and is the pattern to look for whenever a problem asks about contiguous runs; the DP introduction covers the general idea.

Implementation that handles the edge cases

A production version should return indices, accept all-negative input and reject empty input explicitly. Initialising best to 0, as many textbook versions do, silently returns 0 for [-3, -1, -2], which is the sum of the empty subarray and not a legal answer under the non-empty convention.

def max_subarray(a):
    """Return (best_sum, start, end_inclusive). Raises on empty input."""
    if not a:
        raise ValueError("max_subarray of an empty sequence")
    best = cur = a[0]
    best_l = best_r = cur_l = 0
    for i in range(1, len(a)):
        if cur < 0:                 # a negative prefix only hurts: restart here
            cur, cur_l = a[i], i
        else:
            cur += a[i]
        if cur > best:
            best, best_l, best_r = cur, cur_l, i
    return best, best_l, best_r


print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # (6, 3, 6)
print(max_subarray([-3, -1, -2]))                       # (-1, 1, 1)

The strict comparison cur > best keeps the earliest maximal subarray when there are ties; switch to >= to keep the latest. Restarting when cur < 0, rather than <= 0, prefers longer runs when a zero-sum prefix could be dropped; flip it for the shortest. Decide which tie-breaking your callers need and test it.

Worked trace

Trace the classic input [-2, 1, -3, 4, -1, 2, 1, -5, 4]. cur starts at -2. At i=1 the previous cur is negative, so restart: cur = 1, best = 1. At i=2, cur = 1 - 3 = -2. At i=3 cur is negative again, so restart at 4; best becomes 4 with start index 3. Then cur runs 3, 5, 6, so best becomes 5 and then 6 at i=6. At i=7 cur falls to 1 and at i=8 rises to 5, neither beating 6. Answer: 6, from a[3..6] = [4, -1, 2, 1].

Why it is correct

The proof is a loop invariant. After processing index i, cur equals the maximum sum of a subarray ending at i, and best equals the maximum sum of any subarray within a[0..i]. Base case: both are a[0], the only subarray. Step: every subarray ending at i is either [a[i]] or some subarray ending at i-1 with a[i] appended; the best of the latter is cur(i-1) + a[i], so the larger of the two is cur(i). Every subarray of a[0..i] either ends at i, covered by cur, or lies within a[0..i-1], covered by the old best. At i = n-1 the invariant gives the answer. Each element is touched once: O(n) time, O(1) space.

Divide and conquer, and segment trees

There is also an O(n log n) divide-and-conquer solution, and it matters because its merge step is what a segment tree stores. Split the array in half. The best subarray lies in the left half, the right half, or straddles the middle. Summarise each segment with four numbers: total sum, best prefix, best suffix and best subarray. Two summaries combine in constant time:

def node(x):                       # (total, best prefix, best suffix, best)
    return (x, x, x, x)

def merge(L, R):
    tot = L[0] + R[0]
    pre = max(L[1], L[0] + R[1])
    suf = max(R[2], R[0] + L[2])
    best = max(L[3], R[3], L[2] + R[1])
    return (tot, pre, suf, best)

def dc(a, lo, hi):
    if lo == hi:
        return node(a[lo])
    mid = (lo + hi) // 2
    return merge(dc(a, lo, mid), dc(a, mid + 1, hi))

print(dc([-2, 1, -3, 4, -1, 2, 1, -5, 4], 0, 8))   # (1, 2, 5, 6)

On a static array, Kadane wins. But store these four-tuples in the nodes of a segment tree and you can answer "maximum subarray sum within a[l..r]" and apply point updates, each in O(log n), which Kadane cannot do without rescanning. The general strategy is covered in divide and conquer. The merge is associative, which also means it parallelises: split a huge array across workers, summarise each chunk, and merge the summaries.

Variants: circular, product and 2D

Circular arrays. If the subarray may wrap around the end, the best wrapping subarray is the total minus the minimum non-wrapping subarray. Take the larger of that and the ordinary answer, with one trap: if every element is negative, total minus minimum is the empty wrap and equals 0, so return the ordinary answer instead.

def max_circular(a):
    best, _, _ = max_subarray(a)
    if best < 0:                    # every element negative: wrap cannot help
        return best
    worst, _, _ = max_subarray([-x for x in a])
    return max(best, sum(a) + worst)   # total minus the minimum subarray

print(max_circular([5, -3, 5]), max_circular([-3, -1, -2]))   # 10 -1

Maximum product. A negative number turns the smallest product into the largest, so track both the maximum and minimum product ending at i and swap them when a[i] is negative. For [2, 3, -2, 4] the answer is 6; for [-2, 3, -4] it is 24.

def max_product(a):
    hi = lo = best = a[0]
    for x in a[1:]:
        if x < 0:
            hi, lo = lo, hi
        hi = max(x, hi * x)
        lo = min(x, lo * x)
        best = max(best, hi)
    return best

Two dimensions. For the maximum-sum rectangle in an r x c matrix, fix a top and bottom row, collapse the columns between them into one array of column sums, and run Kadane on it. That is O(r^2 c) time; put the smaller dimension in the squared term.

def max_rectangle(m):
    rows, cols = len(m), len(m[0])
    best = m[0][0]
    for top in range(rows):
        col = [0] * cols
        for bottom in range(top, rows):
            for j in range(cols):
                col[j] += m[bottom][j]     # column sums of rows top..bottom
            s, _, _ = max_subarray(col)
            best = max(best, s)
    return best

print(max_rectangle([[1, 2, -1, -4, -20],
                     [-8, -3, 4, 2, 1],
                     [3, 8, 10, 1, 3],
                     [-4, -1, 1, 7, -6]]))   # 29

The table summarises when each approach is the right one.

Kadane's also works on a stream: it needs only the current element, so it can run over data that never fits in memory and report the best run seen so far at any moment.

Failure modes

• Initialising best to 0. Wrong for all-negative input unless your specification explicitly allows the empty subarray.
• Overflow. In fixed-width languages, prefix sums of a long array of large values overflow 32-bit integers; use 64-bit accumulators.
• Floating point. Running sums accumulate rounding error, and comparisons between nearly equal candidates can flip. Use compensated summation or compare with a tolerance if indices must be stable.
• Stale start index. Updating the start index when best improves, instead of when cur restarts, reports the wrong range while returning the right sum. Test indices, not only sums.
• Circular all-negative case. The wrap formula returns 0, an empty answer.

Where it shows up

The best time to buy and sell a stock once is the maximum subarray of day-to-day price differences. In genomics, scoring each base and finding maximal-scoring segments locates regions rich in a property of interest. In monitoring, subtracting a baseline from a metric and running Kadane finds the window where it most exceeded normal, a simple alternative to fixed-width windows, which sliding-window techniques handle when the width is fixed.

What to do next

1. Implement max_subarray from memory with index tracking and check it against a brute-force O(n^2) version on random arrays, including all-negative ones.
2. Write down your empty-input and tie-breaking contract and add tests for both.
3. Implement the prefix-sum version and extend it to "length at least k".
4. Solve the circular and maximum-product variants and test the all-negative case of each.
5. Build a segment tree with the four-tuple merge and answer range queries with point updates.
6. Apply the 2D rectangle reduction to a small matrix and verify against brute force.