What is Kadane's algorithm for the maximum subarray sum?
At each element decide: extend the running subarray or start fresh from this element. Track the best sum seen. It finds the largest contiguous sum in one pass.
Explain it simply
Imagine your daily profit and loss from a tea stall. You want the best stretch of consecutive days. While your running total is positive it is helping you, so keep adding. Once it goes negative it only drags the next days down, so drop it and start again from today.
In code that is one line: the best sum ending here is max(current element, previous best + current element).
Example
function maxSubArray(nums) {
let current = nums[0];
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
best = Math.max(best, current);
}
return best;
}
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // Output: 6
console.log(maxSubArray([-5, -2, -9])); // Output: -2Complexity
Time O(n), space O(1).
What to say in the interview
"For each position I keep the best sum of a subarray ending there: either the element alone or the element added to the previous best. The answer is the largest of those values. It is O(n) time, O(1) space, and it handles all-negative arrays if I start from the first element rather than zero."
Common mistakes
- Initialising best to 0, which returns 0 for an all-negative array instead of the largest negative number.
- Confusing subarray (contiguous) with subsequence.