Kadane's Algorithm Interview Pattern: Maximum Subarray Explained
"Find the contiguous subarray with the largest sum" is one of the most common coding interview prompts, and it's a gateway to a whole family of problems. The efficient answer is Kadane's algorithm: a single pass, constant space, and a short idea you can explain in one sentence.
This guide covers the Kadane's algorithm interview pattern: how it works, when to use it, the variants interviewers like, and how to talk through it clearly.
The brute force, briefly
Start by naming the obvious approach, as you would in a real interview. Check every subarray: pick a start, pick an end, sum the elements. With running sums that's O(n²); without them it's O(n³). It works, but for large inputs it's too slow.
Saying this first shows you understand the problem, and it gives you a baseline to improve on.
The core idea
Walk through the array once. At each index, ask: is it better to extend the best subarray ending at the previous index, or to start fresh here?
If the best sum ending at the previous index is negative, it only drags the current element down, so start over. Otherwise, extend.
That's the whole algorithm. Track two values:
current: the best sum of a subarray ending at this indexbest: the best sum seen anywhere so far
A clean template
def max_subarray(nums):
current = best = nums[0]
for x in nums[1:]:
current = max(x, current + x)
best = max(best, current)
return best
Time is O(n) and extra space is O(1).
Note the initialization: starting best at nums[0] instead of 0 handles arrays where every value is negative. If you initialize to 0, an input like [-3, -1, -2] would wrongly return 0. Ask the interviewer whether an empty subarray is allowed; if it is, 0 can be the right answer, and that's exactly the kind of clarifying question worth asking.
Explaining it out loud
A concise talk track:
"At each position I keep the best sum of a subarray that ends exactly here. That's either the element alone or the element plus the best sum ending just before it. Whichever is larger becomes the new current. I also track the global best. One pass, constant space."
Then dry run on [-2, 1, -3, 4, -1, 2, 1, -5, 4]:
| x | current | best |
|---|---|---|
| -2 | -2 | -2 |
| 1 | 1 | 1 |
| -3 | -2 | 1 |
| 4 | 4 | 4 |
| -1 | 3 | 4 |
| 2 | 5 | 5 |
| 1 | 6 | 6 |
| -5 | 1 | 6 |
| 4 | 5 | 6 |
The answer is 6, from the subarray [4, -1, 2, 1].
Why it works (the DP view)
Kadane's is dynamic programming with the table compressed to one variable. Define dp[i] as the maximum sum of a subarray ending at index i. Then dp[i] = max(nums[i], dp[i-1] + nums[i]), and the answer is the maximum over all dp[i]. Since each state depends only on the previous one, you only need one variable.
Mentioning this connection is useful when interviewers ask "why is this correct?" It also helps you derive variants instead of memorizing them.
Returning the indices
A common follow-up: return the subarray itself, not just the sum. Track where the current subarray started:
- When you start fresh (
x > current + x), setstart = i. - When
currentbeatsbest, recordbest_start = startandbest_end = i.
Practice this once; it's easy to get the index updates in the wrong order under pressure.
Variants interviewers like
Maximum product subarray. Negative numbers flip signs, so the smallest product can become the largest after multiplying by a negative. Track both the current max and current min at each step, and swap them when the element is negative.
Circular maximum subarray. The best subarray either doesn't wrap (regular Kadane) or wraps around the end. A wrapping subarray equals the total sum minus the minimum subarray. Compute both and take the larger, but watch the edge case: if all numbers are negative, the "total minus minimum" option corresponds to an empty subarray, so return the regular Kadane result instead.
Maximum sum with at most one deletion. Keep two states: best sum ending here with no deletion, and best sum ending here with one deletion used. Each updates from the previous step.
Best time to buy and sell a stock (single transaction). Convert prices to daily differences, and the answer is the maximum subarray of those differences (or zero, if no profit is possible). Many candidates solve it with a running minimum instead, which is equivalent.
When to reach for this pattern
Signals in the prompt:
- "Contiguous subarray" plus "maximum" or "minimum" sum
- A running quantity where a bad prefix should be dropped
- Profit, gain, or score over consecutive days
When the problem says "subsequence" instead of "subarray," elements don't have to be contiguous, and Kadane's usually doesn't apply directly. When the problem asks for a subarray with sum exactly equal to a target, prefix sums with a hash map are typically the better fit.
Common mistakes
- Initializing
bestto 0 when all-negative arrays are possible - Updating
bestbeforecurrent - Forgetting the min-tracking in product variants
- Missing the all-negative edge case in the circular version
Practice the explanation, not just the code
Kadane's is short enough to memorize, which is exactly why interviewers probe the reasoning and the variants. Practice explaining the "extend or restart" decision out loud with a timer running. Luna Interview gives you a structured way to rehearse that and stay composed when a follow-up changes the problem.
Quick checklist
- [ ] Brute force named with its complexity
- [ ] "Extend or restart" idea stated in one sentence
- [ ] Initialization handles all-negative input
- [ ] Dry run on a mixed example
- [ ] Indices version practiced once
- [ ] Product and circular variants understood
Once the core idea clicks, a surprising number of "hard-looking" array problems turn into one careful pass.
Rehearse with an AI interview copilot, then browse commonly reported interview questions.