Kadane's Algorithm Maximum Subarray
Fast recall
Quick revision
Core answer
currentSum: at each element take max(num, currentSum + num) - either extend the running subarray or restart at the current number - and track the best sum seen. The restart is the key idea: a negative running sum can only hurt, so drop it.Whether you know Kadane's restart rule and can handle the all-negatives edge case
Initializing maxSum to 0 (breaks on all-negative arrays) or not understanding when to restart
Explain the restart as 'a negative prefix is dead weight' and initialize maxSum to the first element
Interview-ready guide
Interview answer
Kadane's algorithm finds the maximum-sum contiguous subarray in one linear pass with constant extra space.
The whole thing hinges on one decision I make at each element: should I extend the subarray I'm currently building, or throw it away and start fresh at the current element? I express that as current sum equals the max of the current number alone, or the current number plus the running sum. The reasoning is that if my running sum has gone negative, it's dead weight.
Adding a negative prefix to whatever comes next only makes things worse, so I abandon it and restart at the current element. Alongside the running sum, I keep a separate best variable that records the highest sum I've ever seen, updating it each step. At the end, best is my answer.
It's O of n time and O of one space. The classic trap, and the thing I'm careful about, is the all-negative array. If I initialize my best to zero, then for an array like negative three, negative one, negative two, I'd wrongly return zero, as if I could pick an empty subarray.
So I initialize both the running sum and the best to the first element of the array, which correctly returns negative one in that case. Another subtlety is that when I restart, I restart at the current number, not at zero, because the subarray has to be non-empty.
If the interviewer also wants the actual subarray and not just the sum, I track the start index whenever I restart and the end index whenever I update the best.
Kadane's Algorithm Maximum Subarray
Direct Answer
Kadane's algorithm finds the maximum-sum contiguous subarray in O(n) time, O(1) space. Walk the array keeping currentSum: at each element take max(num, currentSum + num) - either extend the running subarray or restart at the current number - and track the best sum seen. The restart is the key idea: a negative running sum can only hurt, so drop it.
Deep Dive & Architecture
Kadane's algorithm keeps two values. current is the best sum of a subarray that must end at the current index. best is the largest sum seen anywhere so far. At each number, either extend the previous range or start a new range at this number:
current = max(value, current + value)
Worked example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
At 4, extending the previous negative sum is worse than restarting, so current becomes 4. Adding -1, 2, and 1 changes it to 3, 5, and 6. That range is [4, -1, 2, 1], so best becomes 6. Adding -5 lowers the ending sum to 1 but does not change the global best.
Initialize both values from the first element, not from zero. With input [-5, -2, -8], zero would incorrectly describe an empty subarray; correct initialization returns -2.
Every item is processed once, giving O(n) time and O(1) extra space. If the question also asks for the actual subarray, record a candidate start whenever a restart occurs and save its boundaries whenever best improves.
Code Example
int maxSubArray(int[] nums) {
int cur = nums[0], best = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]); // extend or restart
best = Math.max(best, cur); // track global best
}
return best;
}
// nums = {-2, 1, -3, 4, -1, 2, 1}
// cur: -2,1,-2,4,3,5,6 (restart at index1 and index3)
// best: -2,1,1,4,4,5,6 -> answer 6 (subarray {4,-1,2,1})
Common Mistakes & Pitfalls
- maxSum = 0 start: fails on all-negative arrays like
{-3,-1,-2}(returns 0 instead of -1). Initialize tonums[0]. - Resetting to 0 instead of
num: restarting at 0 ignores the current element; restart atnum. - Confusing with max product: Kadane is for sums; max product needs to track min too (negatives flip signs).
- Returning the subarray: if asked for indices, track start/end when you restart and when you update best.
Check your understanding
Answer these without looking back at the article.
- What is the time complexity of common array operations in Java?
- How do you reverse a string in Java without using built-in reverse methods?
- How do you find duplicates in an array in Java?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.