Kadane's Algorithm

The shape of the problem

Given an integer array (possibly with negative numbers) find the contiguous subarray with the largest sum. The subarray must be non-empty. Brute force enumerates every (l, r) pair, which is O(n²); a slightly sharper brute force computes prefix sums and then asks "which two prefix entries differ by the most?", still O(n²). Kadane's algorithm answers in O(n) with a single line of state.

The reason the problem feels harder than it is: the answer interacts with negatives. If all elements are non-negative, the answer is the sum of the whole array, trivial. The presence of negatives means a great subarray can be ruined by a stretch of negatives in the middle, which is exactly the question Kadane's transition resolves.

The state and the transition

Define f(i) to be the maximum sum of a subarray that ends at index i. This forced ending is the trick, it lets us speak about local subproblems instead of the global answer. The transition then has two cases:

• The best subarray ending at i extends the best subarray ending at i − 1: f(i) = f(i − 1) + a[i].
• The best subarray ending at i starts fresh at i: f(i) = a[i].

So f(i) = max(a[i], f(i − 1) + a[i]). The global answer is max(f(i)) across all i.

Implementation

def max_subarray(a):
    best_here = best_overall = a[0]
    for x in a[1:]:
        best_here = max(x, best_here + x)
        best_overall = max(best_overall, best_here)
    return best_overall

Two scalars, one pass. best_here is f(i); best_overall is the running maximum of f. The initialisation matters, both start at a[0] because the first subarray ending at index 0 is just {a[0]}. Using 0 instead would silently break on all-negative inputs (you'd return 0 for an array like [-3, -1, -2] when the correct answer is -1).

Why it's correct, in one sentence

The transition max(a[i], f(i − 1) + a[i]) is equivalent to: "if the running total is negative, throw it away." A negative running total cannot help any future subarray, adding any number to a negative makes it smaller than just starting from that number. So abandoning a negative running total never costs us the optimum. Conversely, a non-negative running total might help, it might combine with a future positive run to beat any local choice. Keeping it is a free option. Greedily taking the max is therefore the optimal local rule.

This is a special case of a deeper principle: when subproblems share an "extend or restart" structure, the optimal decision at each step depends only on the sign of the running aggregate, not on its full history. That principle is also why dynamic programming works in general, local optimal decisions compose into a global optimum when subproblems overlap and have optimal substructure.

Complexity, reasoned

Time: O(n). One pass through the array, two comparisons and one addition per element. Space: O(1) extra, two scalars. Both are tight; you can't beat O(n) since you must inspect every element to know whether it changes the answer.

Variant, circular subarrays

The "max sum circular subarray" variant lets the subarray wrap around the array's end. Two cases handle every possibility:

• The maximum subarray is non-wrapping. Standard Kadane suffices.
• The maximum subarray wraps around. Equivalent to "remove a contiguous middle subarray with the smallest sum", which is total_sum − min_subarray, where min_subarray is found by running Kadane's with negation.

def max_circular(a):
    def kadane(b):
        best_here = best = b[0]
        for x in b[1:]:
            best_here = max(x, best_here + x)
            best = max(best, best_here)
        return best
    total = sum(a)
    max_normal = kadane(a)
    min_normal = -kadane([-x for x in a])
    if max_normal < 0:
        return max_normal             # all-negative case: don't wrap
    return max(max_normal, total - min_normal)

The all-negative guard is essential. If every element is negative, the "wrap" case computes total − total = 0 (empty subarray), but the problem requires a non-empty subarray. Without the guard you'd return 0, wrong.

Variant, maximum product subarray

The product variant breaks the simple Kadane recurrence because negatives flip signs. A negative running product can become enormously positive when multiplied by another negative. The fix is to track two running aggregates, the maximum and the minimum product ending at i.

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

The swap when x < 0 is the whole insight. A negative x turns the largest existing product into the smallest and vice versa, so we swap before applying the max/min transitions. Two scalars, still O(n), still O(1) memory.

When to reach for Kadane's

Whenever a problem asks for "the best contiguous subarray that satisfies some monotone property" and the property has an extend-or-restart structure, Kadane's pattern fits. Common signals:

• The brute force is O(n²) over (l, r) pairs and the per-pair work is O(1).
• The optimum can shift abruptly (a long run of negatives mid-sequence), that's the "restart" case.
• The state per element is a scalar, not a structure.

Where beginners go wrong

• Initialising to 0 instead of a[0]. Returns 0 on all-negative inputs. The problem usually requires non-empty subarrays.
• Tracking only one running aggregate for the product variant. A negative running product is a positive in disguise; you must track both extremes.
• Forgetting the all-negative guard in the circular variant. The wrap-around shortcut produces zero, which is invalid for non-empty subarrays.
• Confusing this DP with prefix sums. Both are O(n), but Kadane's needs no array, two scalars suffice. Prefix sums answer "what is the sum of a given range?", Kadane's answers "what is the best range?"

What to read next

Prefix sums are the natural sibling, both reduce O(n²) range queries to O(n). Dynamic programming generalises the "extend or restart" idea into a much larger family of recurrences. And the worked problem Maximum Subarray shows the algorithm applied to its canonical interview form, with the brute-force ladder, the divide-and-conquer alternative, and edge-case discussion.