Kadane's Algorithm

Find the contiguous subarray with the largest sum in one pass: at each element, either extend the best subarray that ends just before it or start over.

Overview

The idea

The maximum subarray problem asks for the contiguous run of elements with the largest sum. Checking every run costs O(n²) time, and there are n(n + 1) / 2 of them: about 5 billion for n = 100,000.

Kadane's algorithm does it in one pass with two numbers. current is the largest sum of any subarray that ends at the element you are looking at. best is the largest current seen so far. At each element there are only two choices: extend the subarray that ends just before it, or start a new one here.

The rule in one line is current = max(nums[i], current + nums[i]). The two branches differ only in whether current from the left is added, and adding it helps exactly when it is positive.

A trace

Run it on [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Both variables start at the first element.

0 — -2 — start — -2 — -2
1 — 1 — -1 — start over — 1 — 1
2 — -3 — -2 — extend — -2 — 1
3 — 4 — 2 — start over — 4 — 4
4 — -1 — 3 — extend — 3 — 4
5 — 2 — 5 — extend — 5 — 5
6 — 1 — 6 — extend — 6 — 6
7 — -5 — 1 — extend — 1 — 6
8 — 4 — 5 — extend — 5 — 6

The answer is 6, from [4, -1, 2, 1]. Notice row 4: current drops to 3 but stays positive, so the -1 is kept and the later 2 and 1 build on it. Notice row 7 as well: after -5, current is 1, still positive, so the final 4 extends it to 5 rather than starting over.

Why it is correct

Every subarray ends somewhere. If you know the best subarray ending at each index, the overall best is the largest of those. And the best subarray ending at index i either is nums[i] alone or is nums[i] glued onto the best subarray ending at i - 1: any other subarray ending at i - 1 would give a smaller total.

That is a dynamic programming recurrence, dp[i] = max(nums[i], dp[i - 1] + nums[i]), and current is dp[i] without the array. Only the previous value is ever read, so O(n) space becomes O(1).

Full DP table — dp[0..n - 1] — dp[i] = max(nums[i], dp[i - 1] + nums[i]) — O(n)
Kadane — current, best — current = max(nums[i], current + nums[i]) — O(1)

All negatives, and the initialization bug

If every element is negative, the answer is the largest single element, which is still negative. That works only when current and best start at nums[0]. Starting them at 0 returns 0, which is the sum of an empty subarray that the usual problem statement does not allow.

0 — -3 — -3 — -3
1 — -1 — -1 — -1
2 — -2 — -2 — -1

On [-3, -1, -2] the answer is -1. If the problem does allow an empty subarray, then 0 is the right answer and starting at 0 is correct, so ask.

Recovering the subarray

A common follow-up asks for which subarray, not just its sum. Track three indexes: where the current run started, and the start and end of the best run. When you start over, the current run starts at i. When current beats best, copy the current start and set the end to i.

0 — -2 — start — -2 — 0 — -2 — 0..0
1 — 1 — start over — 1 — 1 — 1 — 1..1
2 — -3 — extend — -2 — 1 — 1 — 1..1
3 — 4 — start over — 4 — 3 — 4 — 3..3
4 — -1 — extend — 3 — 3 — 4 — 3..3
5 — 2 — extend — 5 — 3 — 5 — 3..5
6 — 1 — extend — 6 — 3 — 6 — 3..6

Update best only on a strict improvement if the problem wants the earliest such subarray; use greater-or-equal to get the latest.

The circular variant

In Maximum Sum Circular Subarray the array wraps, so a subarray may take a piece from the end and a piece from the start. There are two cases.

The wrapping case is the trap. If every element is negative, the minimum subarray is the whole array, total - min is 0, and 0 is an empty subarray. In that case return the plain Kadane answer alone.

[5, -3, 5] — 7 — -3 — 7 — 10 — 10
[1, -2, 3, -2] — 3 — -2 — 0 — 2 — 3
[3, -1, 2, -1] — 4 — -1 — 3 — 4 — 4
[-3, -2, -3] — -2 — -8 — -8 — 0 — -2 (all negative, keep max)

Maximum product

Products behave differently: a negative times a negative is positive, so the smallest product so far can become the largest after one more negative. Keep both the largest and the smallest product ending at i, and consider three candidates at each step.

nums[i] — start over
maxEnding × nums[i] — extend the largest
minEnding × nums[i] — extend the smallest; wins when nums[i] is negative

This trace runs on [-2, 3, -4].

0 — -2 — -2 — -2 — -2
1 — 3 — 3, -6, -6 — 3 — -6 — 3
2 — -4 — -4, -12, 24 — 24 — -12 — 24

A zero resets both to 0, which is right: nothing that includes the zero can beat starting over after it. On [-2, 0, -1] the answer is 0.

Kadane as a prefix-sum problem

A subarray sum is a difference of two prefix sums, so the largest subarray ending at j is prefix[j] - min(prefix[0..j - 1]). Scanning with a running minimum of the prefixes is the same algorithm in a different coat.

0 — -2 — -2 — 0 — -2 — -2
1 — 1 — -1 — -2 — 1 — 1
2 — -3 — -4 — -2 — -2 — 1
3 — 4 — 0 — -4 — 4 — 4
4 — -1 — -1 — -4 — 3 — 4
5 — 2 — 1 — -4 — 5 — 5
6 — 1 — 2 — -4 — 6 — 6
7 — -5 — -3 — -4 — 1 — 6
8 — 4 — 1 — -4 — 5 — 6

This view is what to reach for when the plain rule does not fit. If the subarray must have at least k elements, the smallest earlier prefix may only come from k or more positions back: keep the running minimum of prefix[0..j - k]. On [1, -2, 3, -1, 2] with k = 2 the answer is 4, from [3, -1, 2], which an exhaustive check confirms. If the subarray must have at most k elements, the minimum over a sliding range of prefixes needs a monotonic deque.

The same shape elsewhere

The pattern is a running best from the left, combined with the current element. Best Sightseeing Pair scores a pair (i, j) with i < j as values[i] + i + values[j] - j. Split it into a left part values[i] + i and a right part values[j] - j, keep the largest left part seen so far, and at each j combine.

1 — 1 — 8 — 8 + 1 - 1 = 8 — 8
2 — 5 — 8 — 8 + 5 - 2 = 11 — 11
3 — 2 — 8 — 8 + 2 - 3 = 7 — 11
4 — 6 — 8 — 8 + 6 - 4 = 10 — 11

On [8, 1, 5, 2, 6] the answer is 11 from the pair (0, 2). Best Time to Buy and Sell Stock is the same shape with the smallest price so far as the left part.

Two dimensions

For the largest-sum rectangle in an m × n matrix, fix a pair of column boundaries, add the rows between them into one number per row, and run Kadane on that column of sums to find the best row range. Trying all column pairs costs O(n²) pairs times O(m) each: O(m · n²), and O(m · n · min(m, n)) if you choose the shorter side for the pairs.

Choose columns left ≤ right — O(n²) pairs
Row sums between them, updated as right grows — O(m) per pair
Kadane on the m row sums — O(m) per pair

How to spot it

Largest sum of a contiguous subarray — Kadane, start both variables at nums[0]
The array is circular — max of Kadane and total minus the minimum subarray, unless all negative
Largest product of a contiguous subarray — track the largest and smallest product ending here
Best pair with a score that splits into a left part and a right part — running best of the left part
Length at least k, or at most k — prefix sums with a lagged running minimum, or a monotonic deque
Best subset, not contiguous — not Kadane; take the positives, or use a different DP

What you will be able to do

Write Kadane from memory and explain the extend-or-restart rule in one sentence.
Handle all-negative input and say when 0 is the right answer instead.
Return the subarray itself with three extra indexes.
Solve the circular and product variants and name their traps.
Recognize the same running-best shape in pair and prefix-sum problems.

When to use it

Largest (or smallest) sum of a contiguous subarray
Largest product of a contiguous subarray, with sign flips
Circular arrays where the subarray may wrap around the end
Any question that reduces to the best subarray ending at each index
Pair scores that split into a left part and a right part, combined with a running best
Length constraints on the subarray, through the prefix-sum view

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio