Kadane's Algorithm: Designed in One Minute, O(n) Maximum Subarray

Ulf Grenander proposed the maximum subarray problem in 1977. Michael Shamos solved it in O(n log n) overnight using divide and conquer. Then at a Carnegie Mellon University seminar where Shamos was presenting the history, Jay Kadane sat in the audience and derived the O(n) solution in under a minute. He reportedly didn't even stand up. That's Kadane's algorithm. It's been in every interview loop since.

The problem: given an integer array (possibly with negatives), find the contiguous subarray with the largest sum. Return that sum. At least one element must be included. Your first instinct is O(n²), trying every start and end index. Everyone's first instinct is O(n²). Kadane's version does it in one pass with two variables, and it's as fast as any correct algorithm can be since you must inspect every element at least once.

Reach for Kadane's whenever a problem asks for a maximum or minimum sum over a contiguous subarray. Reach for it also when a problem looks like something else entirely, because the stock-profit problem, the circular array problem, and a handful of other LeetCode favorites all reduce to it once you see the transformation.

The O(n³) Brute Force and Why It Falls Apart

For every pair (i, j), sum up nums[i..j] and track the max. Summing naively is O(n) per pair, giving O(n³) total. With prefix sums, the inner sum becomes O(1), but you still try every (i, j) pair, so it's O(n²). Both are wrong answers, just at different speeds.

Shamos's divide-and-conquer splits the array at the midpoint, recurses on each half, and finds the maximum crossing subarray in O(n) time. This yields the recurrence T(n) = 2T(n/2) + O(n), which Master Theorem case 2 solves to O(n log n). Better. But not Kadane.

Kadane's question was simpler than "what's the best subarray from i to j?" He asked: what is the best subarray ending exactly at position i?

The Core Insight: Best Subarray Ending Here

Call the maximum sum of any subarray ending at index i current[i]. Computing it is almost trivial. Any subarray ending at i either:

1. Consists of just nums[i] alone (start fresh), or
2. Extends the best subarray ending at i-1 by appending nums[i].

The second option yields current[i-1] + nums[i]. Take the better one:

dp[i] = max(nums[i], dp[i-1] + nums[i])

The answer to the full problem is max(dp[0], dp[1], ..., dp[n-1]). And since dp[i] only depends on dp[i-1], you don't need the full array. One scalar suffices.

The decision rule simplifies to: if the running total is negative, it hurts any element you add to it, so discard it and restart. Negative baggage is just baggage. Cut it. If the running total is non-negative, extending always helps or at worst breaks even.

Stated as code:

if current < 0: current = nums[i]     # restart
else:           current += nums[i]    # extend

Both branches are equivalent to current = max(nums[i], current + nums[i]).

At each position: negative running total means restart, non-negative means extend. Both branches collapse to max(nums[i], current + nums[i]).

Tracing Through the Canonical Example

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] (LeetCode 53's example)

Index:    0    1    2    3    4    5    6    7    8
Value:   -2    1   -3    4   -1    2    1   -5    4

Action:  init  NEW  ext  NEW  ext  ext  ext  ext  ext
current: -2    1   -2    4    3    5    6    1    5
best:    -2    1    1    4    4    5    6    6    6

Red = restart (current was negative). Green = extend. The best row is a high-water mark: it only moves up.

At index 1: current = -2, so current + 1 = -1 < 1. Restart. current = 1. At index 3: current = -2, so current + 4 = 2 < 4. Restart. current = 4. At index 7: current = 6 + (-5) = 1. Still extends (1 > -5). Best stays 6.

The winning subarray is [4, -1, 2, 1] at indices 3-6, with sum 6.

Why This Is Provably Optimal

The argument is an exchange argument on the dp recurrence.

Claim: dp[i] equals the maximum sum over all subarrays ending at i.

Base case: dp[0] = nums[0]. Only one subarray ends at 0 (itself), and its sum is nums[0].

Inductive step: assume dp[i-1] is the maximum sum of any subarray ending at i-1. Any subarray ending at i either starts at i (sum = nums[i]) or includes position i-1. If it includes i-1, it consists of some subarray ending at i-1 followed by nums[i]. The best such prefix is dp[i-1], giving dp[i-1] + nums[i]. So dp[i] = max(nums[i], dp[i-1] + nums[i]).

The global answer is max over all dp[i]. The O(1) space reduction works because dp[i] depends only on dp[i-1], so we overwrite in place.

Each dp[i] depends only on dp[i-1]. The full array is never needed, so we overwrite a single variable in place.

O(n) Time, O(1) Space, and Why That's Optimal

Time is O(n) because the loop makes one pass. No element is revisited. No nested loops. Every update is O(1). The lower bound is also Ω(n) because any algorithm that ignores even one element can be defeated by an adversary who puts an arbitrarily large value there. Kadane matches the lower bound.

Space is O(1) because dp[i] depends only on dp[i-1]. The rolling scalar trick is exactly the space-optimization technique described for any linear recurrence: instead of keeping the full dp table, keep only the last value.

The 2D variant fixes a pair of rows (r1, r2) and collapses the matrix column-by-column: col_sum[j] is the sum of column j between rows r1 and r2. Run Kadane on the resulting 1D array. Iterating over all O(n²) row pairs with O(m) Kadane each gives O(n²m) time and O(m) space for the column sum array.

The Bug That Has Ended Interviews

Run the standard "initialize to 0" version on nums = [-3, -2, -5]:

# WRONG: zero initialization
current = best = 0
for num in nums:
    current = max(num, current + num)
    best = max(best, current)
# Returns 0, not -2

Zero is not a valid subarray sum. Zero is the answer when you haven't included any elements, which the problem explicitly forbids. The answer for an all-negative array is the least-negative element. Always initialize current and best to nums[0], then loop from index 1.

# Correct
current = best = nums[0]
for num in nums[1:]:
    current = max(num, current + num)
    best = max(best, current)

For [-3, -2, -5], this returns -2. Correct.

There is a version of Kadane's that allows an empty subarray, treating 0 as a valid baseline. That form initializes to 0 and is appropriate when "take nothing" is a legal choice. Most interview problems (including LeetCode 53) specify at least one element, so the nums[0] form is the right default.

A 2023 paper (Kadane, "Two Kadane Algorithms for the Maximum Sum Subarray Problem," MDPI Algorithms) documents that the algorithm Kadane originally intended at that CMU seminar allows the empty subarray. The version popularized by Bentley in "Programming Pearls" (CACM 1984) does not. Both are O(n), O(1), and correct for their respective problem definitions.

Zero is not a subarray. It is the answer you get when you haven't read the problem statement carefully enough.

Tracking the Actual Subarray

The standard algorithm returns only the sum. Returning the start and end indices of the winning subarray adds two extra scalars and one extra condition.

def max_subarray_with_bounds(nums: list[int]) -> tuple[int, int, int]:
    current = best = nums[0]
    temp_start = start = end = 0

    for i in range(1, len(nums)):
        if nums[i] > current + nums[i]:   # restart
            current = nums[i]
            temp_start = i
        else:                              # extend
            current += nums[i]

        if current > best:
            best = current
            start = temp_start
            end = i

    return best, start, end

temp_start records where the current running window started. It only gets committed to start when the current window beats the best. For [-2, 1, -3, 4, -1, 2, 1, -5, 4], this returns (6, 3, 6): subarray [4, -1, 2, 1] from index 3 to index 6.

One Structure, Every Language

def max_subarray(nums: list[int]) -> int:
    current = best = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        best = max(best, current)
    return best

Which Problems Reduce to Kadane's?

The algorithm applies to any problem reducible to "find the maximum (or minimum) sum of a contiguous segment." The canonical form is LeetCode 53. Every other case requires a translation.

Maximum subarray sum. The base case. Two scalars, one loop, done.

Minimum subarray sum. Replace both max calls with min. Or negate every element, run the standard form, and negate the result. Both approaches are O(n), O(1).

Best single-transaction stock profit (LC 121). Build the array of daily changes where changes[i] = prices[i] - prices[i-1]. The profit from buying on day b and selling on day s equals the sum of changes from b+1 through s. So the maximum profit equals the maximum subarray sum of the changes array. One transformation, then standard Kadane.

Maximum circular subarray sum (LC 918). A subarray that wraps around from the end of the array to the beginning is the complement of a contiguous middle segment. Since the wrapped subarray and the middle it skips must cover the whole array together, maximizing the wrap is equivalent to minimizing the middle. The formula is max(kadane_max, total_sum - kadane_min). Run Kadane once for max, once for min, and apply the formula.

def max_circular_subarray(nums: list[int]) -> int:
    def kadane_max(arr: list[int]) -> int:
        current = best = arr[0]
        for num in arr[1:]:
            current = max(num, current + num)
            best = max(best, current)
        return best

    def kadane_min(arr: list[int]) -> int:
        current = best = arr[0]
        for num in arr[1:]:
            current = min(num, current + num)
            best = min(best, current)
        return best

    max_sum = kadane_max(nums)
    min_sum = kadane_min(nums)
    total = sum(nums)

    # If all elements are negative, min_sum == total,
    # and total - min_sum == 0 (empty subarray, invalid).
    if total == min_sum:
        return max_sum

    return max(max_sum, total - min_sum)

The visual intuition: a wrapping subarray is everything except some contiguous middle chunk. Maximizing the outside means minimizing the inside, which is exactly a minimum subarray problem. See the worked example below for the diagram.

Maximum sum submatrix. Fix a pair of row boundaries r1 and r2. Compute col_sum[j] as the sum of column j between those rows. Run Kadane on col_sum. Repeat for all O(n²) row pairs. Total: O(n²m) time, O(m) space for the column sums.

Maximum product subarray (LC 152). This is not direct Kadane, but it uses the same per-position structure. For sums, a negative current hurts all future extensions. For products, a negative current can become helpful: multiply it by another negative and it flips to a large positive. So you must track both max_prod and min_prod ending at each position. The new max is max(nums[i], max_prod * nums[i], min_prod * nums[i]), and similarly for min. One extra variable, same O(n) time and O(1) space.

When to Reach for Kadane's Algorithm

Three signals that Kadane's applies:

Signal 1: The problem asks for the maximum (or minimum) sum over a contiguous segment of an array. The phrasing might say "subarray," "consecutive elements," or "contiguous subsequence."

Signal 2: The array has negative elements that break naive greedy accumulation. A sliding window won't work here. Shrinking from the left doesn't help when the entire running sum has gone negative.

Signal 3: A non-obvious problem transforms into a maximum subarray problem once you reframe its elements. This is the signal most candidates miss. They solve LC 121 with a rolling minimum, get the right answer, and walk out certain they understand this algorithm. The follow-up question finds them.

Worked Example 1: Best Time to Buy and Sell Stock (LC 121)

Problem: prices = [7, 1, 5, 3, 6, 4]. Buy once, sell once. Return max profit.

The brute-force reading is: for every pair (buy_day, sell_day) where buy_day < sell_day, compute prices[sell_day] - prices[buy_day]. That's O(n²).

Transform: Build the daily changes array.

prices:  7    1    5    3    6    4
changes: --  -6   +4   -2   +3   -2

changes = [-6, 4, -2, 3, -2]

The profit from buying at day b and selling at day s equals prices[s] - prices[b], which telescopes to the sum of changes from day b+1 to day s. So the maximum profit equals the maximum subarray sum of changes.

Apply Kadane's:

current: -6    4    2    5    3
best:    -6    4    4    5    5

Max sum = 5. The subarray [4, -2, 3] corresponds to buying at price 1 (day 1) and selling at price 6 (day 4).

The daily-changes transformation makes the profit problem identical to maximum subarray. Buy and sell dates fall out naturally from the subarray bounds.

Note: most engineers who solve LC 121 correctly track a rolling minimum price instead. That's equivalent to Kadane's but without recognizing the connection. Being right by accident still passes the interview. It's less useful when the follow-up asks for at most k transactions and you have no idea why the original solution worked.

Worked Example 2: Maximum Sum Circular Subarray (LC 918)

Problem: nums = [5, -3, 5]. The subarray can wrap around from the end to the beginning. Find the maximum sum.

Case 1 (no wrap): Standard Kadane.

current: 5    2    7
best:    5    5    7

Best non-wrapping sum = 7 (the entire array).

Case 2 (wrap): A wrapping subarray from index 2 to index 0 (in circular order) skips only the middle. The wrapped sum equals total_sum - (sum of skipped middle). To maximize the wrap, minimize the middle.

total_sum  = 5 + (-3) + 5 = 7
kadane_min = -3               (the minimum subarray is just [-3])
circular   = 7 - (-3) = 10

max(7, 10) = 10. The winning wrap-around subarray is [5, 5] with sum 10.

Edge case validation: Try nums = [-3, -2, -5].

• kadane_max = -2 (the least negative element)
• kadane_min = -10 = total_sum
• total - min = 0 (the "wrap" covers nothing, empty subarray, invalid)
• Return kadane_max = -2

Maximizing the wrap = minimizing what you leave out. The skipped middle is a Kadane minimum problem in disguise.

Recap

• Kadane's runs in O(n) time and O(1) space. The lower bound is also Ω(n), so it is optimal.
• The recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i]), compressed to a rolling scalar.
• The decision at each step: if current < 0, restart. If current >= 0, extend.
• Initialize to nums[0], not 0. Zero is not a valid answer when all inputs are negative.
• For index tracking, maintain temp_start, start, and end alongside the sum variables.
• Circular variant: max(kadane_max, total - kadane_min). Guard against the all-negative case where total == kadane_min.
• Stock profit (LC 121) is Kadane's in disguise: convert prices to daily changes first.
• Product subarray (LC 152) uses the same per-position structure but tracks both max_prod and min_prod because negative times negative flips sign.
• The minimum subarray variant: replace max with min throughout, or negate the array.

Practicing these variants on paper is one thing. Explaining the "total minus minimum" insight clearly under pressure, out loud, to a person watching you, while an interviewer probes why the all-negative guard is necessary, is where preparation usually falls short. SpaceComplexity runs voice-based mock interviews with rubric-based feedback on exactly that kind of live reasoning, not just whether the code compiles.

For the DP mechanics behind the rolling-scalar trick, bottom-up dynamic programming covers the general pattern of compressing a dp table to its look-back horizon. Five coding interview problems where your first solution isn't optimal traces when Kadane's beats brute force, including the CMU seminar derivation. For related linear-pass techniques that use a window rather than a running sum, sliding window technique covers the O(n) patterns that operate on fixed or variable-width windows.

Further Reading

• Maximum subarray problem - Wikipedia
• Largest Sum Contiguous Subarray - GeeksforGeeks
• LeetCode 53: Maximum Subarray
• LeetCode 918: Maximum Sum Circular Subarray
• LeetCode 152: Maximum Product Subarray