Kadane's Algorithm Explained: Maximum Subarray in O(n)

Kadane’s algorithm solves the maximum subarray problem: given an array of numbers, find the contiguous slice with the largest sum. It does this in a single left-to-right pass, using constant extra memory, for O(n) time overall. The core idea fits in one sentence — at each position, either extend the best subarray ending at the previous position or start fresh here, whichever is larger.

The problem

Take this array:

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

The contiguous subarray with the largest sum is [4, -1, 2, 1], which adds up to 6. Note that it includes a negative number: dropping the -1 would split the run and lose the 4 or the 2, 1 on one side.

“Contiguous” is the key word. If you could pick any subset of elements, you’d just take all the positive numbers. Requiring a single unbroken slice is what makes the problem interesting.

The brute-force approaches

The obvious solution checks every subarray. There are roughly n²/2 start-end pairs, and summing each one naively costs O(n), giving O(n³). Keeping a running sum as you extend the end index brings it down to O(n²).

A divide-and-conquer solution reaches O(n log n): split the array in half, recursively solve each half, and also compute the best subarray crossing the midpoint. It’s a nice exercise, but Kadane beats it with simpler code. (For a refresher on what these growth rates mean in practice, see Big O notation.)

The key insight

Define best_ending_here[i] as the maximum sum of any subarray that ends exactly at index i. There are only two possibilities for that subarray:

1. It’s just arr[i] on its own.
2. It’s the best subarray ending at i - 1, extended by arr[i].

So:

best_ending_here[i] = max(arr[i], best_ending_here[i - 1] + arr[i])

Equivalently: if the best sum ending at the previous position is negative, it can only hurt, so throw it away and start over at arr[i].

The answer to the full problem is the largest best_ending_here value seen at any index. Since each step only needs the previous value, you don’t need an array — two variables suffice.

That recurrence is a textbook example of dynamic programming: an optimal answer built from optimal answers to smaller subproblems, computed bottom-up, with the table compressed down to a single running value.

The code

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

The same thing in JavaScript:

function maxSubarray(arr) {
  let endingHere = arr[0];
  let best = arr[0];
  for (let i = 1; i < arr.length; i++) {
    endingHere = Math.max(arr[i], endingHere + arr[i]);
    best = Math.max(best, endingHere);
  }
  return best;
}

Walking through the example

Index	Value	best_ending_here	best_overall
0	-2	-2	-2
1	1	1 (restart)	1
2	-3	-2	1
3	4	4 (restart)	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

The algorithm restarts at index 3 because the running sum ending at index 2 was negative. From there it carries the run through the -1 because the total stays positive, peaks at 6, and never beats that.

Edge cases worth getting right

• All negative numbers. Some versions initialize the running sum to 0 and reset to 0 whenever it goes negative. That returns 0 for [-3, -1, -2], which is only correct if the empty subarray is allowed. Initializing both variables to arr[0], as above, correctly returns -1.
• Empty input. Decide what the function should do — throw, or return a sentinel — and handle it before reading arr[0].
• Overflow. In languages with fixed-width integers, large inputs can overflow the running sum. Use a wider type if values can be large.
• Floating point. The algorithm works on floats too, with the usual floating-point caveats around accumulated rounding.

Recovering the subarray itself

Often you need the indices, not just the sum. Track where the current run started, and record the start and end whenever best_overall improves:

def max_subarray_with_indices(arr):
    best_ending_here, best_overall = arr[0], arr[0]
    start = best_start = best_end = 0
    for i in range(1, len(arr)):
        if arr[i] > best_ending_here + arr[i]:
            best_ending_here = arr[i]
            start = i
        else:
            best_ending_here += arr[i]
        if best_ending_here > best_overall:
            best_overall = best_ending_here
            best_start, best_end = start, i
    return best_overall, best_start, best_end

Common variations

Kadane’s pattern shows up in many disguises:

• Maximum product subarray. Track both the maximum and minimum product ending at each index, because a negative number can turn the smallest product into the largest.
• Circular arrays. The best circular subarray is either a normal Kadane result or the total sum minus the minimum subarray (found with the same algorithm, flipped). Handle the all-negative case separately.
• Best time to buy and sell a stock once. Convert prices into day-over-day differences and run Kadane on them; the maximum subarray sum is the maximum profit.
• Maximum sum rectangle in a 2D grid. Fix a pair of rows, collapse the columns between them into a 1D array of sums, and run Kadane — O(rows² × cols).

How it relates to other techniques

Kadane is sometimes confused with the sliding window technique, since both scan once and maintain a running range. The difference is the decision rule: a sliding window shrinks from the left under a constraint, while Kadane abandons the entire prefix at once when it goes negative. It also overlaps with prefix sums — the maximum subarray equals the largest difference between a prefix sum and the smallest earlier prefix sum. If you need maximum-subarray queries over arbitrary ranges of a changing array, a segment tree storing Kadane-style summaries per node is the standard tool.

The takeaway

Kadane’s algorithm finds the maximum-sum contiguous subarray in O(n) time and O(1) space by keeping one running value: the best sum ending at the current position, which either extends the previous run or restarts. Initialize from the first element to handle all-negative input, track a start index if you need the slice itself, and look for the same “extend or restart” structure in product, circular, and stock-profit problems.