vault

Kadane's Algorithm

15 min read

Kadane’s Algorithm

Kadane’s algorithm finds the contiguous subarray with the largest sum in O(n) time and O(1) extra space — the fastest possible. The trick is a one-line dynamic-programming recurrence: at each index i, the maximum-sum subarray ending exactly at i is either arr[i] alone (start fresh) or arr[i] + best_ending_at(i-1) (extend the previous best). Take the maximum across all i and you have the global answer. The algorithm was discovered in the early 1980s and popularized by Jon Bentley in Programming Pearls (1986), who used it as the prototype example of how an algorithm’s running time can drop from O(n³) brute force to O(n²) (precomputed sums) to O(n log n) (divide and conquer) to O(n) (Kadane’s clever reformulation) — a four-step descent that has become a textbook narrative.

1. Intuition — A Gambler’s Streak

Imagine you’re a sports gambler keeping a running ledger as the season unfolds. Each game you either win money (positive) or lose money (negative). At the end of the season you want to identify the single longest streak of consecutive games that netted you the most money.

You walk forward through the season day by day with two pieces of paper:

  • Current run: how much you’d have made if your “current betting streak” started somewhere in the past and continues through today.
  • Best run ever: the maximum value the current run has ever reached.

When today’s result comes in, ask one question: “is my current run, plus today, better than starting a fresh streak from today?” If yes, extend. If no — i.e., the current run is dragging today’s potential down — abandon it and reset: today is the new start.

That’s Kadane. The “abandon” rule is the entire algorithm: a running sum that dips below zero is worse than nothing, so throw it away. Specifically, once current_sum + arr[i] < arr[i] (which happens exactly when current_sum < 0), starting fresh from arr[i] is strictly better.

The deeper point: Kadane reduces a problem about all O(n²) subarrays to a single O(n) walk by recognizing that the optimal subarray ending at position i is built from the optimal subarray ending at position i − 1 in a one-step decision. This is the prototypical Dynamic Programming subproblem: “best answer ending exactly here.”

2. Tiny Worked Example

Take arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4] (the LC 53 textbook example).

iarr[i]best_ending_herebest_so_farReasoning
0−2−2−2initialize
11max(1, −2 + 1) = 11reset (prior was negative)
2−3max(−3, 1 + −3) = −21extend (1 + −3 = −2 > −3)
34max(4, −2 + 4) = 44reset
4−1max(−1, 4 + −1) = 34extend
52max(2, 3 + 2) = 55extend
61max(1, 5 + 1) = 66extend
7−5max(−5, 6 + −5) = 16extend (barely positive)
84max(4, 1 + 4) = 56extend

Answer: 6, attained by the subarray [4, −1, 2, 1] (indices 3..6).

Notice how best_ending_here is itself a running quantity that can dip — at index 2 it’s −2 — but the global answer best_so_far only ever climbs (or stays flat). Two bookkeeping variables, one pass.

3. The Pattern Recognition Signal

Reach for Kadane (or a Kadane variant) when any of these phrases or shapes appear:

  1. “Maximum subarray sum” — the canonical statement.
  2. “Largest contiguous sum,” “max sum contiguous subarray” — synonyms.
  3. “Maximum subarray product” — variant with two running states (since multiplying by a negative flips sign).
  4. “Best time to buy and sell stock” (LC 121, single transaction) — equivalent to Kadane on the price-difference array (subtle but classical).
  5. “Maximum circular subarray sum” (LC 918) — Kadane plus a complement trick.
  6. “Longest positive-sum subarray” — Kadane variant tracking length instead of sum.
  7. “Maximum sum rectangle in a 2D matrix” (LC 363) — Kadane invoked O(R²) times after column-prefix-sum compression.
  8. Any problem with the structure “choose a contiguous range to maximize an additive quantity, with a clear penalty for including ‘bad’ elements” — Kadane is the right shape.

The inverse signals — when Kadane is the wrong tool:

  • The subarray must be non-contiguous (subsequence) — that’s a different DP.
  • The problem asks for the longest (not the largest sum) under some property — sliding window or DP on length is more direct.
  • The aggregation isn’t additive (max, min, count of distinct) — Kadane’s “extend or reset” recurrence depends on + being the combiner.

4. Pseudocode

kadane(arr):
    best_ending_here := arr[0]
    best_so_far      := arr[0]
    for i in 1 .. length(arr) - 1:
        best_ending_here := max(arr[i], best_ending_here + arr[i])
        best_so_far      := max(best_so_far, best_ending_here)
    return best_so_far

Two scalars, one pass. No allocations.

Equivalent Reset-on-Negative Form

A semantically equivalent variant that some find easier to read:

kadane_reset(arr):
    current := 0
    best    := -INFINITY
    for x in arr:
        current := current + x
        if current > best:
            best := current
        if current < 0:
            current := 0
    return best

This form makes the “abandon when running sum goes negative” rule explicit. It works because current + x < x exactly when current < 0, so resetting to 0 (and then adding x) is equivalent to the max(arr[i], best_ending_here + arr[i]) reformulation. The catch: this version assumes at least one element exists and the answer might be negative — best is initialized to -INFINITY and only the running-sum check (not the reset) updates it. If you forget this and reset before checking, you’ll wrongly return 0 for an all-negative array.

5. Python Implementation

5.1 Standard Kadane

def max_subarray(arr: list[int]) -> int:
    best_ending_here = best_so_far = arr[0]
    for x in arr[1:]:
        best_ending_here = max(x, best_ending_here + x)
        best_so_far = max(best_so_far, best_ending_here)
    return best_so_far

The recurrence best_ending_here = max(x, best_ending_here + x) is the entire algorithmic idea. Everything else is bookkeeping.

5.2 Kadane with Subarray Indices

If the problem also asks which subarray achieves the max, track the start/end:

def max_subarray_with_indices(arr: list[int]) -> tuple[int, int, int]:
    best_ending_here = best_so_far = arr[0]
    cur_start = best_start = best_end = 0
    for i in range(1, len(arr)):
        x = arr[i]
        if x > best_ending_here + x:
            best_ending_here = x
            cur_start = i                          # reset starts a new subarray here
        else:
            best_ending_here = best_ending_here + x
        if best_ending_here > best_so_far:
            best_so_far = best_ending_here
            best_start = cur_start
            best_end = i
    return best_so_far, best_start, best_end

The cur_start advances on every reset; the best_start/best_end only advance when a strictly better global answer is found. This separation is what makes the index-tracking version unambiguous when there are ties.

5.3 Maximum Product Subarray (LC 152)

The product variant breaks the simple Kadane recurrence because multiplying by a negative number flips sign — the “best ending here” might come from the worst (most negative) prior product times a new negative. So we track both the running max and the running min.

def max_product(nums: list[int]) -> int:
    cur_max = cur_min = best = nums[0]
    for x in nums[1:]:
        # When x < 0, max and min swap roles after multiplication.
        candidates = (x, cur_max * x, cur_min * x)
        cur_max = max(candidates)
        cur_min = min(candidates)
        best = max(best, cur_max)
    return best

Notice that all three candidates (x, max*x, min*x) are considered for both the new max and the new min, in the same iteration. This is critical: if you compute cur_max first and then use the updated cur_max to compute cur_min, you’ve corrupted the recurrence. Compute both from the previous values atomically.

5.4 Maximum Circular Subarray Sum (LC 918)

The array wraps around: the answer might be a contiguous subarray that crosses the seam from the end back to the start. Two cases:

  1. Non-circular max — standard Kadane on the array.
  2. Circular max — the subarray wraps. Equivalently, the complement (the part you exclude) is a contiguous middle subarray with the minimum sum. So: total_sum − min_subarray_sum.

The answer is the larger of the two. Edge case: if all elements are negative, the “circular max” formula gives 0 (excluding everything), which is wrong — you must return the global max element instead.

def max_subarray_sum_circular(nums: list[int]) -> int:
    total = sum(nums)
    # Non-circular Kadane
    cur_max = best_max = nums[0]
    cur_min = best_min = nums[0]
    for x in nums[1:]:
        cur_max = max(x, cur_max + x)
        best_max = max(best_max, cur_max)
        cur_min = min(x, cur_min + x)
        best_min = min(best_min, cur_min)
    if best_max < 0:                                # all-negative array
        return best_max
    return max(best_max, total - best_min)

5.5 Maximum Sum Rectangle in a 2D Matrix (LC 363’s cousin)

For a 2D matrix, “max sum rectangle” reduces to Kadane: fix two row boundaries (r1, r2), compute the column-sum array between those rows, run Kadane on it. Loop over all O(R²) row pairs:

def max_sum_rectangle(matrix: list[list[int]]) -> int:
    R, C = len(matrix), len(matrix[0])
    best = float("-inf")
    for r1 in range(R):
        col_sums = [0] * C
        for r2 in range(r1, R):
            for c in range(C):
                col_sums[c] += matrix[r2][c]
            # Kadane on col_sums
            cur = best_here = col_sums[0]
            for c in range(1, C):
                cur = max(col_sums[c], cur + col_sums[c])
                best_here = max(best_here, cur)
            best = max(best, best_here)
    return best

Total complexity: O(R² × C). For square matrices, that’s O(n³) — much better than the naive O(n⁶) (enumerate all rectangles, sum each).

6. Complexity

Time: O(n). A single pass over the array, constant work per element.

Space: O(1). Two scalar variables (or four if tracking indices).

Why this beats brute force. Bentley’s Programming Pearls (chapter 8, “Algorithm Design Techniques”) narrates four solutions to the maximum-subarray problem, each strictly faster than the last:

ApproachTimeIdea
Brute force enumerationO(n³)Triple loop: every (l, r) pair, sum from scratch
Cumulative sum reuseO(n²)Triple loop, but precompute prefix sums for O(1) inner sum
Divide and conquerO(n log n)Recursive: max in left half, in right half, or crossing the midpoint
KadaneO(n)One pass, two scalars

This four-step descent — explicitly demonstrating that algorithmic improvement, not hardware, dominates real-world performance — is one of the most-cited expository sequences in algorithm design. Bentley credits Jay Kadane (a Carnegie Mellon statistician) for the O(n) solution, which Kadane reportedly produced in a minute when Bentley described the problem to him in 1977.

For n = 10⁶: brute force is 10¹⁸ ops (centuries of CPU time); Kadane is 10⁶ (milliseconds).

Why O(1) space matters. The naive DP formulation might be tempted to allocate a dp[] array of size n storing best_ending_here[i]. But each iteration only depends on the previous value, so a single scalar suffices. This is the classic “rolling-window optimization” in DP — recognize when only O(1) of the DP table is live at any time and drop the rest.

7. Variants and Sub-patterns

7.1 Maximum Subarray with At Most K Elements

Constrain the subarray length to ≤ K. Becomes a sliding-window-of-Kadane hybrid. Bookkeeping more involved; the max-window structure (Sliding Window §7.1) helps.

7.2 Maximum Sum with No Two Adjacent Elements (House Robber, LC 198)

Different recurrence: dp[i] = max(dp[i-1], dp[i-2] + arr[i]). The “extend or skip” structure mirrors Kadane’s “extend or reset,” but the constraint changes the recurrence. Also O(n) time, O(1) space.

7.3 Best Time to Buy and Sell Stock — Single Transaction (LC 121)

Equivalent to running Kadane on the differences prices[i] - prices[i-1]. Profit = max sum of a contiguous slice of differences (since differences telescope: sum(prices[j] - prices[j-1] for j in (l, r]) equals prices[r] - prices[l]). The reduction is elegant and worth knowing as an interview answer.

7.4 Longest Subarray with Positive Product (LC 1567)

Tracks running length of subarrays with positive and with negative product, updating as each new element flips signs. Same “extend or reset” structure but tracking lengths rather than sums.

7.5 Smallest Subarray Sum

Just run Kadane with min instead of max. Useful as a sub-routine in circular max subarray (§5.4) and in “subarray sum closest to zero” (LC 1099 variant).

7.6 Concatenated K-Times Maximum Subarray (LC 1191)

If you concatenate the array K times, the maximum subarray either lies entirely within one copy, spans two copies, or for K ≥ 3 includes the entire middle (if total sum is positive) plus some boundary tails. Reduces to K = 1 and K = 2 Kadanes plus a (K - 2) × total tail bonus.

7.7 Maximum Subarray Sum After One Deletion (LC 1186)

Allow zero or one element deletion. Track two states: best ending here with no deletion and best ending here with one deletion. Two intertwined Kadane recurrences.

8. Pitfalls

8.1 All-Negative Arrays

The reset-on-negative form (§4 second variant) wrongly returns 0 for an all-negative array if you initialize best = 0 and reset before checking. The fix: initialize best = -infinity and update before the reset. The standard max(arr[i], best_ending_here + arr[i]) form (§4 first variant) handles this correctly because best_ending_here starts at arr[0] (negative) and the first iteration is correct.

The LC 53 problem statement explicitly says “the array contains at least one number,” and the answer should be the maximum even if all are negative. Some interviewers add “subarray must be non-empty” — note the constraint.

8.2 Empty-Array Handling

If arr is empty, the answer is undefined. Decide with the interviewer up front: raise an exception, return 0, or return None. The standard form crashes on arr[0] with empty input.

8.3 Updating Both States from Stale Values (Product Variant)

In max_product, cur_max and cur_min must be computed from the previous cur_max and cur_min simultaneously. If you compute cur_max first and then use the updated cur_max in computing cur_min, the algorithm silently produces wrong answers on inputs with negatives. Best practice: compute the three candidates (x, cur_max * x, cur_min * x) first as a tuple, then assign cur_max and cur_min from it.

8.4 Integer Overflow

For arrays with large values and long runs, the running sum can overflow 32-bit integers. Python’s arbitrary-precision integers make this moot, but in C++/Java use long long/long. LC 53 inputs are bounded such that 32-bit suffices, but variants on larger inputs may not be.

8.5 Misidentifying the Problem as Kadane

Not every “maximum sum” problem is Kadane. If the subarray must be non-contiguous (subsequence), Kadane doesn’t apply — that’s a 0/1-style DP. If aggregation is non-additive (max element, count of distinct), the recurrence breaks. Kadane needs the linearity of sum to permit the “extend or reset” decision to be local.

8.6 Off-by-One in Index Tracking

When tracking start/end indices, two common bugs: (a) cur_start updated after the reset check, leaving it at the previous index; (b) best_start updated only on strict improvement (>), missing ties — sometimes desired (first occurrence), sometimes not (the longest). Read the problem statement carefully.

8.7 Confusing Kadane with Maximum Sum Subsequence

The classic subsequence problem (no contiguity required) has trivial answer for non-empty arrays: the sum of all positive elements (and the largest if all are negative). It’s not Kadane. Don’t confuse.

8.8 Circular Variant Edge Case

The “circular max = total − min subarray” formula returns 0 (the empty complement) when all elements are negative — wrong. Special-case: if best_max < 0, return best_max directly. Forgetting this edge case is the most common LC 918 failure.

9. Diagram — The Running Maxima

flowchart LR
    I0["i=0\narr=−2\nbeh=−2\nbsf=−2"] --> I1["i=1\narr=1\nbeh=1\nbsf=1"]
    I1 --> I2["i=2\narr=−3\nbeh=−2\nbsf=1"]
    I2 --> I3["i=3\narr=4\nbeh=4 (reset)\nbsf=4"]
    I3 --> I4["i=4\narr=−1\nbeh=3\nbsf=4"]
    I4 --> I5["i=5\narr=2\nbeh=5\nbsf=5"]
    I5 --> I6["i=6\narr=1\nbeh=6\nbsf=6"]
    I6 --> I7["i=7\narr=−5\nbeh=1\nbsf=6"]
    I7 --> I8["i=8\narr=4\nbeh=5\nbsf=6"]

What this diagram shows. The state of best_ending_here (beh) and best_so_far (bsf) at every index of the standard [-2, 1, -3, 4, -1, 2, 1, -5, 4] example. The key visual is the reset at i = 3: best_ending_here jumps from -2 to 4 because extending the previous run would have given -2 + 4 = 2, less than starting fresh from 4. After that reset, best_ending_here climbs steadily to 6 over the contiguous block [4, −1, 2, 1], which is the answer. The algorithm never has to look back to identify the start of the optimal subarray — the reset point implicitly defines it. best_so_far is monotonically non-decreasing throughout (a global maximum can only grow), while best_ending_here can move freely up and down.

10. Common Interview Problems

#ProblemVariant
LC 53Maximum SubarrayCanonical Kadane
LC 121Best Time to Buy and Sell StockKadane on differences
LC 152Maximum Product SubarrayMin/max dual tracking
LC 198House RobberAdjacent-skip variant DP
LC 213House Robber IICircular variant
LC 918Maximum Sum Circular SubarrayTotal − min subarray
LC 1186Maximum Subarray Sum with One DeletionTwo-state Kadane
LC 1191K-Concatenation Maximum SumK-copies trick
LC 1567Max Length Subarray With Positive ProductLength tracking
LC 363Max Sum Rectangle ≤ K2D Kadane + ordered set
LC 1186Max Subarray Sum After One DeletionAugmented state
LC 134Gas StationReset-on-negative variant
LC 1546Max Number of Non-Overlapping Subarrays Sum=KGreedy + prefix sums
LC 1493Longest Subarray of 1s After DeletingLength analog
LC 689Maximum Sum of 3 Non-Overlapping SubarraysDP with O(n) per subarray
LC 2272Substring With Largest VarianceCleverly disguised Kadane
LC 2606Find the Substring With Maximum CostMap chars to scores, then Kadane
LC 1191 (concat)Concatenated array KadaneSee §7.6

The “Substring With Largest Variance” problem (LC 2272) is a beautiful disguised-Kadane example: variance = (count of one char) − (count of another), reduce to maximum-sum subarray with +1/−1 mapping. Worth studying.

11. Open Questions

  • Is there a clean characterization of “Kadane-friendly” problems beyond “linear, additive, contiguous”? The disguised forms (LC 121, LC 2272) suggest the family is wider than the literal statement of LC 53.
  • How does Kadane generalize to weighted DAGs (longest path with weights)? The structure is similar — the answer at a node depends on the best incoming neighbor — but topological order replaces array order.
  • What is the optimal complexity for the 2D max-sum-rectangle problem? Currently O(R² × C); can it be improved without strong assumptions on the matrix?

12. See Also

Graph View

Backlinks