Maximum subarray sum: Kadane's algorithm

The idea: the best run that ends here

The maximum subarray problem asks for the contiguous run a[l..r] with the largest sum. In −2 1 −3 4 −1 2 1 −5 4 it is 4 −1 2 1, sum 6. Trying every run costs n(n+1)/2 windows. Kadane's algorithm finds the answer in one sweep from left to right, with a few variables and no table.

Extend or start fresh

Let cur[i] be the largest sum of a run that ends at index i. Such a run is either a[i] alone, or the best run ending at i − 1 with a[i] added. So

cur[i] = max(a[i], cur[i−1] + a[i])

That is a one-dimensional dynamic program, and each cell needs only the one before it, so a single variable cur is enough. The choice is simple: start fresh exactly when cur[i−1] < 0, because a negative run can only drag a[i] down. When cur[i−1] = 0 both choices tie; the page extends. In the canvas the choice row shows "extend" (blue) or "fresh" (orange), and the orange span is the current run s..i. (Demo: classic −2 1 −3 4 −1 2 1 −5 4)

Keeping the best and its range

The answer is the largest cur[i] over all i. Keep best next to cur, and also remember s, the index where the current run started (it changes on every fresh start). When cur beats best, the best window becomes [s, i]. The page uses a strict ">", so on a tie the earliest window wins. The sweep reads each element once: O(n) time, O(1) extra space.

cur = best = a[0]; s = l = r = 0
for i in 1 .. n-1:
    if cur < 0: cur = a[i]; s = i      # start fresh
    else:       cur = cur + a[i]         # extend
    if cur > best: best = cur; l = s; r = i

A negative element does not end a run by itself. In 4 −1 −2 5 the run dips to 1 but stays positive, so it carries on and reaches 6, more than the 5 alone. (Demo: a dip worth crossing) When the input swings hard, the run restarts again and again: 2 −3 4 −5 6 −7 3 2 starts fresh at 4, 6 and 3, and the best is the single 6. (Demo: reset-heavy)

Edge cases

input	what happens	answer
all negative −3 −5 −1 −4 −2	every cur is negative, so every step starts fresh	−1, the largest single element
all positive 2 3 1 4 2	cur never drops below 0, so the run never restarts	12, the whole array
empty run allowed	start with cur = best = 0 and use cur = max(0, cur + a[i])	0 when all are negative

Which version you want depends on the problem. Starting with best = a[0] (as here) forces a non-empty run. (Demo: all negative; Demo: all positive)

Why one sweep is enough

Brute force sums every window: O(n³), or O(n²) with prefix sums. Divide and conquer splits the array in half and takes the best of the left half, the right half and the best run crossing the middle: O(n log n). Kadane is O(n) because cur[i] already summarizes every run ending at i: of all those runs, only the best one can matter later. A segment tree stores the same summary (total, best prefix, best suffix, best) per node, so it can answer "maximum subarray in a[l..r]" after updates.

Relatives: circular and product

Maximum circular subarray. When the array wraps around, the best run either does not wrap (plain Kadane) or wraps. A wrapping run is everything except a middle run, so its sum is total − minimum subarray, and the minimum subarray is Kadane with min in place of max. Take the larger of the two, except when every element is negative (then the "everything except" run is empty).

Maximum product subarray. A negative number turns the smallest product into the largest, so keep both: hi = max(a[i], hi·a[i], lo·a[i]) and lo = min(a[i], hi·a[i], lo·a[i]), using the old hi and lo. A zero resets both.

See also Longest Increasing Subsequence, another DP over "the best answer that ends at i", and Plain Recursion vs Memoization vs Tabulation, where a bottom-up table also shrinks to a couple of variables.

What the page leaves out

Inputs are capped at 12 numbers from −99 to 99 so the bars fit. The page leaves out the circular and product versions (described above but not animated), the maximum-sum rectangle in a 2D matrix (Kadane over every pair of rows, O(n³)), the k largest subarray sums, the maximum subarray with a length limit (a sliding-window minimum of prefix sums), and the parallel version that combines (total, prefix, suffix, best) summaries.

References

Maximum subarray problem (Wikipedia)

Jon Bentley, Programming Pearls: Algorithm Design Techniques, CACM 1984

Search the subarray with the maximum/minimum sum (cp-algorithms)