Kadane and Maximum Subarray

Kadane’s algorithm is the shortest useful algorithm in the interview canon: three lines, $O(n)$ time, $O(1)$ space, and it answers “what is the largest sum any contiguous subarray can have?” over arrays that contain negative numbers — where a sliding window cannot go.

The whole thing rests on one decision made once per element:

Does the best subarray ending here extend the previous one, or start fresh at me?

If the running sum you inherit is negative, it can only drag you down, so you restart. That is it. Everything else on this page is that idea wearing a different hat.

What you’ll learn

• The extend-or-restart decision, and why it is provably optimal.
• Kadane framed as a one-line DP — which is how you extend it.
• Why the all-negative case breaks a naive implementation.
• The three big variants: product (signs flip), circular (wrap around), and absolute value.
• Three real LeetCode problems solved in the browser: 53, 152, 918.

The cue

You are looking at Kadane when…

• “Maximum/largest sum of a contiguous subarray” — 53.
• The array contains negatives (otherwise the answer is trivially the whole array, and it is not really a question).
• You want the best subarray, not a count of them. (Counting is prefix sums + a hash map.)
• A product, absolute value, or circular version of the same — 152, 1749, 918.
• Disguised: “best day to buy and sell a stock once” (121) is Kadane over the array of day-to-day differences.

The pattern

kadane_template.py

def max_subarray(nums):
    best = current = nums[0]        # NOT 0 -- see the all-negative note
    for x in nums[1:]:
        current = max(x, current + x)   # restart at x, or extend by x
        best = max(best, current)
    return best
 
 
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # 6  -> [4, -1, 2, 1]
print(max_subarray([-3, -1, -2]))                       # -1 -> [-1]

current means the best sum of any subarray ending exactly at this index. best is the best of those over all indices. Two variables, one pass.

The all-negative trap

Initialising best = 0 is the classic bug. On [-3, -1, -2] it returns 0, implying the empty subarray — but LeetCode 53 requires a subarray of at least one element, so the answer is -1.

Start both variables at nums[0] and iterate from index 1. Equivalently, best = float("-inf"). Never 0, unless the problem explicitly permits an empty subarray — and if it is ambiguous, ask, because it is a real specification question, not a trick.

Why extend-or-restart is optimal

Let current[i] be the largest sum of a subarray ending at index i. Any such subarray either is just nums[i], or is a subarray ending at i-1 extended by nums[i]. The best of the second kind is current[i-1] + nums[i]. So

$\text{current}[i] = \max\big(\text{nums}[i],\ \text{current}[i-1] + \text{nums}[i]\big)$

and the answer is $\max_i \text{current}[i]$. That is a complete DP, and because current[i] depends only on current[i-1], the table collapses to one variable — which is why the space is $O(1)$.

Reading it as a DP is what lets you extend it: for the product variant you simply need two rolling states instead of one.

	Time	Space
Every subarray, summed	$O(n^3)$	$O(1)$
Every subarray, running sum	$O(n^2)$	$O(1)$
Divide and conquer	$O(n \log n)$	$O(\log n)$
Kadane	$O(n)$	$O(1)$

Visual intuition

One question per step: is it better to extend the run I am on, or throw it away and start fresh here? Watch the frames where the run restarts.

arrayExtend, or restart — one decision per elementLC 53 · O(n) time, O(1) space

cur -2

-2011-3243-142516-5748

i

1def max_subarray(arr):2    best = cur = arr[0]3    for v in arr[1:]:4        cur = max(v, cur + v)   # extend, or restart at v5        best = max(best, cur)6    return best

cur-2best-2

seedSeed with the first element. Kadane's asks one question per step: is it better to extend the run I am on, or throw it away and start fresh here?

Play‹›1/10⟲

The restart happens exactly when the running total has gone negative: a negative prefix can only drag down whatever follows, so dropping it is always at least as good. That single observation is the whole algorithm.

Complexity

Approach	Time	Space	Note
Every subarray, summed from scratch	$O(n^3)$	$O(1)$	the naive triple loop
Every subarray, running sum	$O(n^2)$	$O(1)$	fine up to a few thousand
Divide and conquer	$O(n \log n)$	$O(\log n)$	worth mentioning; rarely the intended answer
Kadane	$O(n)$	$O(1)$	one pass, two variables

Kadane’s is optimal: any correct algorithm must read every element at least once, so $O(n)$ is a lower bound.

The variant map

Variant	What changes	Canonical problem
Maximum sum	The base template	53 Maximum Subarray
Maximum product	Track max and min; a negative swaps them	152 Maximum Product Subarray
Circular	Answer is max(best_max, total - best_min), guarded	918 Maximum Sum Circular Subarray
Maximum absolute sum	max(best_max, -best_min)	1749
Return the indices	Record start when you restart, and (start, i) when best improves	53 follow-up
Minimum sum	Flip every max to min	Used as a subroutine by 918

Why the product variant needs two states

For sums, a large current is always what you want. For products, a very negative running product is valuable — one more negative factor turns it into a large positive. So track both hi and lo, and when x < 0, swap them before updating, because multiplying by a negative turns the largest into the smallest and vice versa. Zeros reset both, which the max(x, ...) / min(x, ...) form handles automatically.

Practice — real LeetCode problems

LC 53 — Maximum Subarray · Medium

Problem. Given an integer array nums, find the contiguous subarray with at least one element that has the largest sum, and return that sum.

Constraints. 1 <= len(nums) <= 10^5, -10^4 <= nums[i] <= 10^4.

Examples. [-2,1,-3,4,-1,2,1,-5,4] gives 6 ([4,-1,2,1]) · [1] gives 1 · [5,4,-1,7,8] gives 23 · [-3,-1,-2] gives -1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

current is the best sum of a subarray ending at the current index. If the inherited current is negative, x alone beats current + x, so the subarray restarts — which is what max(x, current + x) expresses without an explicit branch.

Time $O(n)$. Space $O(1)$.

The [-3,-1,-2] case is the whole reason to be careful with initialisation. Every current is negative, every restart is negative, and the correct answer is the least bad single element.

Follow-ups you should expect:

• “Return the subarray, not the sum.” Keep a start that resets to i whenever you restart, and record (start, i) whenever best improves.
• “Do it with divide and conquer.” LeetCode explicitly asks for this. Split in half; the answer is the best of (left half, right half, best crossing subarray), where the crossing one is found by expanding outward from the midpoint. $O(n \log n)$ — strictly worse, but it is a legitimate demonstration of the technique and a common ask.
• “What if the array is a stream?” Kadane is already online: it needs only the current element and two numbers of state.
• “At most k elements?” No longer Kadane — that is a windowed DP needing a monotonic deque.

LC 152 — Maximum Product Subarray · Medium

Problem. Given an integer array nums, find the contiguous subarray with the largest product, and return that product.

Constraints. 1 <= len(nums) <= 2 * 10^4, -10 <= nums[i] <= 10. The answer fits in a 32-bit integer.

Examples. [2,3,-2,4] gives 6 ([2,3]) · [-2,0,-1] gives 0 · [-2,3,-4] gives 24 (the whole array) · [0,2] gives 2

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Sums are monotonic under extension; products are not. Multiplying by a negative number inverts the ordering, so the smallest product so far is a genuine candidate for the largest product next. Carrying only hi throws away exactly the information you need on [-2,3,-4], where the answer uses both negatives.

So maintain:

• hi = largest product of a subarray ending here,
• lo = smallest product of a subarray ending here.

When x < 0, swap them first. Then update both against x alone (which is the “restart here” option) and against the extended product.

Time $O(n)$. Space $O(1)$.

Two details that look cosmetic and are not

Swap before updating, not after. Once hi has been overwritten using the old hi, the information lo needed is gone.

max(x, hi * x) handles zeros for free. After a 0, both hi * x and lo * x are 0, and max(x, 0) / min(x, 0) restart cleanly from the next element. An explicit “if x == 0: reset” branch is unnecessary — though [-2,0,-1] (expected 0) is the case that proves whichever approach you took actually works.

Follow-ups you should expect: “Why not divide by the outgoing element to slide a window?” — because a zero makes division undefined and destroys the invariant. “Maximum absolute sum (1749)?” — run Kadane for max and min, and return max(best_max, -best_min). “Count of negatives approach?” — there is a neat prefix/suffix-scan solution too, worth mentioning: scan left-to-right and right-to-left, resetting on zeros, and take the best product seen.

LC 918 — Maximum Sum Circular Subarray · Medium

Problem. Given a circular integer array nums, return the maximum sum of a non-empty subarray. The subarray may wrap from the end back to the beginning, but may not include any element more than once.

Constraints. 1 <= len(nums) <= 3 * 10^4, -3 * 10^4 <= nums[i] <= 3 * 10^4.

Examples. [1,-2,3,-2] gives 3 · [5,-3,5] gives 10 (wraps) · [-3,-2,-3] gives -2 · [-2,4,-5,4,-5,9,4] gives 15

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Split into two cases:

1. The answer does not wrap. Then it is ordinary Kadane: best_max.
2. The answer wraps. Then the elements it excludes form a single contiguous, non-wrapping block in the middle. Maximising the wrapped sum is therefore the same as minimising the excluded block: total - best_min.

Run Kadane twice in the same pass — once with max, once with min — and return the better of the two candidates.

Time $O(n)$, single pass. Space $O(1)$.

The all-negative case is not optional

If every element is negative, the minimum subarray is the whole array, so total - best_min == 0 — which corresponds to choosing the empty subarray, and the problem requires a non-empty one. On [-3,-2,-3] the unguarded formula returns 0 instead of -2.

The guard if best_max < 0: return best_max is exactly the test “was every element negative?”, since best_max is negative only in that case. This is the single most-failed detail on LC 918.

Follow-ups you should expect: “Why can’t you just concatenate the array with itself and run Kadane?” — because that permits subarrays longer than n, reusing elements; you would need a length cap, which turns it into a windowed DP with a monotonic deque. “Return the indices?” — track them in both Kadanes and report from whichever branch won. “Circular minimum subarray?” — mirror the whole argument.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 2606 inverts the trap on purpose

Almost every Kadane problem forbids the empty subarray, so best = 0 is wrong. LC 2606 permits it, so best = 0 is right. Same algorithm, opposite initialisation — which is why “can the subarray be empty?” is a genuinely useful clarifying question rather than a formality.

6 problems

1 easy5 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○121Best Time to Buy and Sell StockeasyKadane over day-to-day differences -- or just track the running minimumNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftbloomberg
• ○53Maximum SubarraymediumThe base template; the all-negative case is the trapNeetCode 150Blind 75LeetCode Top Interview 150amazonmicrosoftbloombergapple
• ○152Maximum Product SubarraymediumTwo rolling states; a negative swaps max and minNeetCode 150Blind 75
• ○918Maximum Sum Circular Subarraymedium`total - min_subarray` for the wrapping case, plus the all-negative guardLeetCode Top Interview 150
• ○1749Maximum Absolute Sum of Any SubarraymediumRun both Kadanes, return `max(best_max, -best_min)`
• ○2606Find the Substring With Maximum CostmediumMap characters to values, then plain Kadane -- here an empty answer *is* allowed, so `0` is a valid floor

Dry run

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The two decision columns are what to show an interviewer.

i	nums[i]	extend (cur + v)	restart (v)	cur	best	decision
0	−2	—	—	−2	−2	seed
1	1	−1	1	1	1	restart — the −2 prefix only hurts
2	−3	−2	−3	−2	1	extend (both bad; extending is less bad)
3	4	2	4	4	4	restart
4	−1	3	−1	3	4	extend
5	2	5	2	5	5	extend
6	1	6	1	6	6	extend — new best
7	−5	1	−5	1	6	extend (still positive, so worth keeping)
8	4	5	4	5	6	extend

Answer 6, from [4, -1, 2, 1] at indices 3..6.

Two observations worth stating out loud:

• The restart at i = 1 and i = 3 happens exactly when cur was negative. That is not a coincidence — cur + v < v is algebraically the same as cur < 0. Some write it as “if cur < 0: cur = 0”, and the two are identical.
• best was last updated at i = 6, three steps before the end. The maximum subarray does not have to end at the last element, which is why best is a separate variable from cur. Returning cur is the classic wrong answer.

Interview follow-ups

They ask	What they’re checking	The answer
“Why does extend-or-restart work?”	Whether you can justify it	It is the DP current[i] = max(nums[i], current[i-1] + nums[i]); a negative inherited sum can only reduce any extension, so discarding it is never worse
“Can the subarray be empty?”	Whether you clarify the spec	Ask. If yes, floor at 0; if no, start from nums[0]. It changes the answer on all-negative input
“Return the subarray itself”	Bookkeeping	Reset start = i on a restart; save (start, i) when best improves
“Divide and conquer version”	Breadth (LC 53 asks explicitly)	Best of left, right, and the best crossing subarray from the midpoint — $O(n \log n)$
“Why two states for the product?”	Depth	Multiplying by a negative inverts the ordering, so the running minimum is a candidate for the next maximum
“Handle a stream”	Practicality	Already online — $O(1)$ state, one element at a time
“At most k elements”	Knowing the boundary	No longer Kadane; it becomes a windowed DP + monotonic deque

Edge-case checklist

• All negative — the headline trap. Answer is the largest single element, not 0.
• Single element — must return that element, even if negative.
• All positive — the answer is the entire array; a sanity check.
• Contains zeros — harmless for sums; the reset case for products.
• Empty subarray allowed? — a real specification question (2606 vs 53); ask rather than assume.
• Wrapping answer covering the whole array (918) — possible when all values are positive; make sure your formula does not exclude everything.
• Two negatives making a positive product (152) — [-2,3,-4] gives 24; the case that catches single-state solutions.

Self-check

pch.quizTag Kadane's algorithm — self-check

1. Why are `cur` and `best` separate variables?

   A For readability only — one variable would work B Because the maximum subarray need not end at the last element, so the running value and the best-ever value differ C Because cur can be negative and best cannot D To handle the empty array case
   pch.quizShowAnswer

   B — Because the maximum subarray need not end at the last element, so the running value and the best-ever value differ — cur is the best subarray ending exactly at i; best is the maximum over all i. Returning cur is the standard wrong answer and it passes any input whose answer happens to end at the last element.

2. The array is all negative: [-3, -1, -4]. What does a correct Kadane return?

   A 0, since the empty subarray sums to 0 B -1, the largest single element, because the subarray must be non-empty C -8, the total D It is undefined
   pch.quizShowAnswer

   B — -1, the largest single element, because the subarray must be non-empty — This is the edge case that catches implementations initialised with best = 0. LC 53 requires a non-empty subarray, so seed both cur and best with nums[0], never with 0. If a problem does allow the empty subarray, 0 is right — clarify which.

3. `cur = max(v, cur + v)` restarts the run. When exactly does that happen?

   A When v is positive B Exactly when cur is negative, since cur + v < v is equivalent to cur < 0 C When v is larger than best D At every local minimum
   pch.quizShowAnswer

   B — Exactly when cur is negative, since cur + v < v is equivalent to cur < 0 — The two formulations — max(v, cur + v) and 'if cur < 0: cur = 0' — are algebraically identical. A negative prefix can only reduce whatever follows it, so discarding it is always at least as good.

4. Now return the subarray itself, not just its sum. What changes?

   A Nothing — the sum determines the subarray B Track a start index that resets on every restart, and record start and end whenever best improves C You must switch to the O(n²) approach D Run Kadane twice, forwards and backwards
   pch.quizShowAnswer

   B — Track a start index that resets on every restart, and record start and end whenever best improves — Three extra variables and no change in complexity. This is the most common follow-up on LC 53, and getting the bookkeeping right — reset start on restart, capture both bounds on improvement — is the whole of it.

5. The array is circular (LC 918). What is the trick?

   A Run Kadane on the array concatenated with itself B The answer is either a normal maximum subarray, or the total minus the minimum subarray — take the larger, guarding the all-negative case C Sort the array first D Use a sliding window of size n
   pch.quizShowAnswer

   B — The answer is either a normal maximum subarray, or the total minus the minimum subarray — take the larger, guarding the all-negative case — A wrapping subarray is exactly the complement of a non-wrapping one, so minimising the middle maximises the wrap. The guard matters: if every element is negative the 'total minus min' branch returns the empty subarray, so fall back to the plain answer.

Recall card

• Cue — “maximum sum / product of a contiguous subarray”, and negative values are allowed (which is what rules out a sliding window).
• Invariant — cur is the best subarray ending exactly at i; best is the maximum over all i.
• Template — cur = max(v, cur + v), then best = max(best, cur). Seed both with nums[0], never with 0.
• Complexity — $O(n)$ time, $O(1)$ space, and optimal.
• Remember — the restart condition is exactly “cur went negative”. Return best, not cur.
• Variants — circular (total − minimum subarray, with an all-negative guard); product (track min and max, because a negative flips them); return the subarray (track start).

Recap

• Kadane is one decision per element: extend the previous subarray, or restart here — current = max(x, current + x).
• It is a collapsed DP, which is why it is $O(n)$ time and $O(1)$ space, and why the variants are just “carry more state”.
• Never initialise to 0 unless the empty subarray is explicitly allowed — otherwise all-negative input returns the wrong answer.
• Product needs two states because negatives invert the ordering.
• Circular reframes a wrapping subarray as the contiguous block it excludes: max(best_max, total - best_min), guarded against all-negative input.
• Kadane finds the best subarray; counting subarrays is prefix sums + a hash map instead.

Next: Cyclic Sort — the trick for arrays that are a permutation of 1..n, where the values themselves tell you where they belong.