Beginner LevelData Structures & Algorithms
How does Kadane's Algorithm find the Maximum Subarray Sum in O(N)?
ā Interview Prompt: Explain Kadane's algorithm, its core decision (extend vs restart subarray), and solve Maximum Subarray Sum.
Kadane's Algorithm solves Maximum Subarray Sum in $O(N)$ time and $O(1)$ space.
Core Decision at each element:
At each position $i$, choose the maximum of:
ā¢
Extend existing subarray:
currentMax + arr[i]ā¢
Start fresh from current element:
arr[i]Track the global maximum across all positions.
The key insight: if the current running sum becomes negative, it can only hurt future elements ā so we reset it.
Code Implementation Example
typescript
function maxSubArray(nums: number[]): number {
let currentMax = nums[0];
let globalMax = nums[0];
for (let i = 1; i < nums.length; i++) {
// Extend or restart at current element
currentMax = Math.max(nums[i], currentMax + nums[i]);
globalMax = Math.max(globalMax, currentMax);
}
return globalMax;
}
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
// Output: 6 (subarray [4,-1,2,1])š”Kadane's Algorithm ā O(N) maximum subarray sum with constant space.
šÆ Interview Key Takeaway
Kadane's Algorithm is the canonical O(N) solution for maximum subarray. It illustrates the "extend vs restart" DP decision pattern.
#DSA#Kadane#Dynamic Programming#Subarray#Beginner
Back to all Data Structures & Algorithms Questionsā