Kadane's Algorithm (Maximum Subarray)

Why the maximum subarray problem matters

The maximum subarray problem asks a deceptively simple question: given an array of numbers — some positive, some negative — which contiguous slice adds up to the most? "Contiguous" is the crux. You cannot cherry-pick elements from anywhere; you must choose a window a[i..j] and take everything in it.

It shows up everywhere once you learn to see it. The largest single-day-to-single-day gain from a stream of daily price changes is a maximum subarray. The most profitable window of a marketing campaign, the noisiest contiguous region of a signal, the highest-scoring local alignment in a strand of DNA — all reduce to "find the best contiguous run." The brute-force answer is embarrassingly slow, and Kadane's is the reason nobody uses the brute-force answer.

The problem has a small piece of computing folklore attached to it. In 1977 Ulf Grenander posed a 2D image-analysis version; the 1D reduction and the O(n²) improvement circulated, and in 1984 Jay Kadane produced the O(n) one-pass solution during a seminar in about a minute of thought. The story is retold in Jon Bentley's Programming Pearls as a case study in how a problem can collapse from O(n³) to O(n) as you keep sharpening your view of it.

How Kadane's algorithm works, step by step

Kadane's keeps just two numbers as it walks the array:

• best_ending_here — the maximum sum of any subarray that ends exactly at the current index. This is the whole trick.
• best_so_far — the maximum sum of any subarray seen anywhere to the left, i.e. the running answer.

At each element a[i] there are exactly two choices for the best subarray ending at i: either extend the best subarray that ended at i-1 by appending a[i], or restart a brand-new subarray consisting of just a[i]. Take whichever is larger:

best_ending_here = max(a[i], best_ending_here + a[i])

Then fold that into the global answer:

best_so_far = max(best_so_far, best_ending_here)

That is the entire algorithm. The reset — choosing a[i] alone — happens precisely when best_ending_here + a[i] < a[i], which simplifies to best_ending_here < 0. In plain terms: if the running sum you have accumulated is negative, it can only drag down whatever comes next, so drop it and start counting from here. A negative prefix is pure liability; a positive prefix is a head start worth carrying.

The dynamic-programming intuition

Kadane's is a genuine dynamic program, and seeing it that way removes any mystery. Define the subproblem

f(i) = the maximum sum of a subarray that ends exactly at index i

Every subarray ends somewhere, so the true answer is max over all i of f(i). The recurrence writes itself: a subarray ending at i is either just a[i], or something ending at i-1 with a[i] tacked on — and the best "something ending at i-1" is exactly f(i-1). Hence

f(i) = max(a[i], f(i-1) + a[i]),  f(0) = a[0]

Because f(i) depends only on f(i-1), the DP "table" is a single rolling variable — the classic space optimization that turns an O(n) table into O(1). That variable is best_ending_here. Kadane's algorithm is nothing more than this recurrence evaluated in place.

A worked example

Take the canonical input [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Watch best_ending_here (BEH) and best_so_far (BSF) evolve:

i	a[i]	Extend vs restart	BEH	BSF
0	-2	start	-2	-2
1	1	max(1, -2+1) → restart	1	1
2	-3	max(-3, 1-3) → extend	-2	1
3	4	max(4, -2+4) → restart	4	4
4	-1	max(-1, 4-1) → extend	3	4
5	2	max(2, 3+2) → extend	5	5
6	1	max(1, 5+1) → extend	6	6
7	-5	max(-5, 6-5) → extend	1	6
8	4	max(4, 1+4) → extend	5	6

The answer is 6, achieved by the subarray [4, -1, 2, 1] spanning indices 3 through 6. Notice how the algorithm carried the small negative dip -1 at index 4 because the prefix 4 was still positive, but restarted at index 3 because the prefix -2 was negative baggage. That single sign test — is the running sum negative? — is the algorithm's entire decision engine.

The all-negative case and the empty-subarray convention

The one place careless implementations break is an array of all negative numbers, e.g. [-8, -3, -6, -2, -5]. There are two legitimate conventions, and you must pick one deliberately:

• Non-empty subarray required (the standard LeetCode 53 rule). The answer is the largest single element — here -2. To get this, initialize best_so_far = a[0] (or -∞) and use best_ending_here = max(a[i], best_ending_here + a[i]). Never initialize the answer to 0.
• Empty subarray allowed. An empty subarray sums to 0, so the answer for an all-negative array is 0. To get this, clamp the running sum with best_ending_here = max(0, best_ending_here + a[i]) and start best_so_far = 0.

The infamous bug is mixing these up: initializing best_so_far = 0 under the non-empty convention, which silently reports 0 for an all-negative input and passes every all-positive test case, so it hides in code review. Decide the convention first, then wire the initialization to match it.

Kadane's vs the other maximum-subarray algorithms

	Kadane's	Brute force	Prefix sums	Divide & conquer
Time	O(n)	O(n²) or O(n³)	O(n)	O(n log n)
Space	O(1)	O(1)	O(1) rolling / O(n) array	O(log n) stack
Passes	1	Many (all pairs i≤j)	1	Recursive halving
Paradigm	Dynamic programming	Exhaustive enumeration	Running minimum prefix	Split, solve, span the mid
Handles negatives	Yes (with correct init)	Yes	Yes	Yes
Best for	The default answer	Teaching / tiny inputs	When you already have prefix sums	Pedagogy / master-theorem demos

The O(n log n) divide-and-conquer solution is a favorite classroom exercise (it splits the array, recursively solves each half, and separately computes the best subarray crossing the midpoint in linear time, giving the recurrence T(n) = 2T(n/2) + O(n)). It is elegant, but Kadane's beats it on both time and simplicity. The prefix-sum method is the same asymptotics as Kadane's and is worth knowing because it reframes the problem: the maximum subarray sum equals max over j of (prefix[j] − min prefix before j), so you sweep tracking the smallest prefix seen so far. Kadane's is that idea compressed into a single rolling variable.

Implementation in Python

def max_subarray(a):
    """Kadane's algorithm. Non-empty subarray required.
    Returns (best_sum, start_index, end_index)."""
    best_ending_here = a[0]
    best_so_far = a[0]
    start = end = 0          # answer window
    cand_start = 0           # start of the current running window

    for i in range(1, len(a)):
        # extend the running subarray, or restart it at a[i]
        if best_ending_here + a[i] < a[i]:
            best_ending_here = a[i]
            cand_start = i           # a negative prefix was dropped
        else:
            best_ending_here += a[i]

        # fold into the global best
        if best_ending_here > best_so_far:
            best_so_far = best_ending_here
            start, end = cand_start, i

    return best_so_far, start, end


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

Only the sum requires O(1) state; the three index variables are book-keeping that let you return the actual subarray without changing the complexity. The best_ending_here + a[i] < a[i] test is equivalent to best_ending_here < 0 — either phrasing works and both trigger the reset.

Extending Kadane's to 2D: the maximum submatrix

The maximum sum rectangle in an R×C matrix looks like a much harder problem, but it decomposes cleanly onto 1D Kadane's. Fix an ordered pair of rows (top, bottom). Collapse every column in that band into a single number — the sum of its entries from top to bottom. Now you have a 1D array of column sums, and the best contiguous run of columns in it, found by Kadane's, is exactly the best submatrix whose vertical extent is [top, bottom].

def max_submatrix(m):
    R, C = len(m), len(m[0])
    best = float('-inf')
    for top in range(R):
        col_sums = [0] * C
        for bottom in range(top, R):
            # accumulate row `bottom` into the running column band — O(C)
            for c in range(C):
                col_sums[c] += m[bottom][c]
            # 1D Kadane's over the collapsed band — O(C)
            cur = col_sums[0]
            local = col_sums[0]
            for c in range(1, C):
                cur = max(col_sums[c], cur + col_sums[c])
                local = max(local, cur)
            best = max(best, local)
    return best

Reusing col_sums across increasing bottom keeps the band-collapse at O(C) amortized per pair, and there are O(R²) row pairs each running an O(C) Kadane's pass, so the whole thing is O(R²·C). The naive four-corner enumeration is O(R²·C²) (or O(R³·C³) without prefix sums), so the Kadane's reduction is a large, practical win.

Common misconceptions and pitfalls

• Initializing the answer to zero under the non-empty convention. This is the single most common Kadane's bug. It returns 0 on all-negative inputs. Seed the answer with a[0] or -∞ instead.
• Confusing maximum subarray with maximum subsequence. Kadane's requires contiguity. If you may pick non-adjacent elements, the answer is trivially the sum of all positive numbers — a different, easier problem.
• Assuming it needs positive numbers. Kadane's is designed precisely for mixed-sign arrays. On an all-positive array the answer is just the whole array, and the running sum never resets.
• Wanting the maximum product subarray with the same code. Products need a second rolling variable for the running minimum, because a negative times a negative can become the new maximum. That is a related but distinct DP.
• Forgetting circular wrap-around. If the array is circular, the answer is either the standard Kadane's result or total_sum − minimum_subarray_sum (the wrap case), taking the larger — with a guard for the all-negative array where the wrap formula degenerates to the empty subarray.