What is Kadane's Algorithm?
Learn how Kadane's algorithm finds the maximum contiguous subarray sum in O(n) time and how to explain it in an interview.
Expected Interview Answer
Kadane's algorithm finds the maximum sum of a contiguous subarray in O(n) time and O(1) space by scanning once and, at each position, deciding whether to extend the current running subarray or start a new one from the current element, then tracking the best sum seen so far.
The core recurrence is current_max = max(nums[i], current_max + nums[i]): at every index you ask whether adding the current element to the running subarray still beats starting fresh at this element alone. If the running sum has dropped below zero, it can only drag future sums down, so it is better to discard it and restart at the current element. A separate global_max variable tracks the best current_max seen across the whole scan, since the optimal subarray does not have to end at the last index. This is a textbook dynamic programming problem because each position's answer depends only on the previous position's answer, letting you solve it bottom-up in a single pass. The algorithm also extends to variants like maximum product subarray (tracking both max and min due to sign flips) and returning the subarray's actual start and end indices.
- O(n) time, single pass over the array
- O(1) extra space, no auxiliary array needed
- Classic example of optimal-substructure dynamic programming
- Extends to related max-subarray variants
AI Mentor Explanation
A batter's innings is scored ball by ball, some balls gaining runs and some losing runs to wickets-adjusted penalties in a fantasy format. Kadane's algorithm is like tracking a running partnership score: after each ball, you decide whether continuing the current partnership still beats starting a brand-new partnership from this ball alone. The moment the running partnership dips below zero, it is dropped and a fresh partnership begins at the next ball, since a negative partnership can only drag future scores down. Across the whole innings you keep a separate note of the best partnership score seen at any point, because the best stretch does not have to end on the final ball.
Step-by-Step Explanation
Step 1
Initialize both trackers
Set current_max and global_max to the first element of the array.
Step 2
Iterate from the second element
At each index, current_max = max(nums[i], current_max + nums[i]).
Step 3
Update the global best
global_max = max(global_max, current_max) after each update.
Step 4
Return the global best
global_max holds the maximum contiguous subarray sum after the full pass.
What Interviewer Expects
- State the O(n) time, O(1) space complexity upfront
- Explain the extend-or-restart decision at each index clearly
- Correctly handle arrays with all negative numbers
- Recognize this as a dynamic programming problem with optimal substructure
Common Mistakes
- Resetting current_max to zero instead of restarting at nums[i], which breaks all-negative arrays
- Forgetting to update global_max on every iteration, not just when a reset happens
- Confusing maximum subarray sum with maximum subsequence sum (subsequence need not be contiguous)
- Not handling an empty array or single-element array as edge cases
Best Answer (HR Friendly)
“Kadane's algorithm finds the best-performing contiguous stretch in a list of numbers by walking through once and, at each step, asking whether to keep building on the current stretch or start a new one right here. I keep two numbers as I go: the best stretch ending right now, and the best stretch seen anywhere so far, which gives the answer in a single pass with no extra memory.”
Code Example
def max_subarray(nums):
current_max = global_max = nums[0]
for num in nums[1:]:
current_max = max(num, current_max + num)
global_max = max(global_max, current_max)
return global_max
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6, from [4, -1, 2, 1]Follow-up Questions
- How would you also return the start and end indices of the best subarray?
- How would you adapt this to find the maximum product subarray instead?
- How would you handle a circular array where the subarray can wrap around?
- Why is Kadane's algorithm considered a dynamic programming solution?
MCQ Practice
1. What is the time complexity of Kadane's algorithm?
A single pass through the array with constant work per element gives O(n) time.
2. In Kadane's algorithm, when should you restart the running sum at the current element instead of extending it?
If current_max + nums[i] is worse than nums[i] alone, the prior running sum was net negative and should be discarded.
3. What does Kadane's algorithm return for an array of all negative numbers, e.g. [-3, -1, -4]?
When every element is negative, the best contiguous subarray is the single largest element.
Flash Cards
What problem does Kadane's algorithm solve? — Finding the maximum sum of a contiguous subarray.
What is Kadane's algorithm's time and space complexity? — O(n) time, O(1) space.
What is the core recurrence in Kadane's algorithm? — current_max = max(nums[i], current_max + nums[i]).
What happens when the running sum goes negative? — It is discarded, and a new subarray starts at the current element.