At every index, decide: extend the current subarray or restart from here. Track local max (currMax) and global best (maxSoFar) in one pass.
ArrayDynamic ProgrammingGreedyTime O(n)Space O(1)
📋 When to Use
Find the maximum sum contiguous subarray
Problem involves local vs global max decision at each step
Array can contain negative numbers — window size is variable
Any "maximum subarray" variant: sum, product, with deletions
💡 The key insight: if extending gives a smaller result than starting fresh (nums[i] alone), it is always better to restart. This greedy choice is optimal.
⚡ Complexity
Time
O(n)
Space
O(1)
Single left-to-right pass. Only two integers maintained: currMax (best ending here) and maxSoFar (best seen anywhere). No auxiliary array needed.
Live Animation · Kadane's Algorithm · LC #53
Problem
Given an integer array nums, find the contiguous subarray with the largest sum and return its sum. The array may contain negative numbers.
Input: nums = [-2, 1, -3, 4, -1, 2, 1] · Answer: maxSoFar = 6, best subarray = [4, -1, 2, 1] (indices 3..6)
Step 1 / —
🌱 Seed (i=0)
➡️ Extend / 🔄 Restart
🏆 New Max
✅ Done
nums = [-2, 1, -3, 4, -1, 2, 1]
Decision
currMax = —
maxSoFar = —
window = —
Click ▶ Play or Next ▶ to start
int maxSoFar = nums[0], currMax = nums[0];
Kadane's Algorithm — Pattern SkeletonJAVA
// Kadane's Algorithm — Maximum Subarray Sumint maxSoFar = nums[0], currMax = nums[0];
for (int i = 1; i < nums.length; i++) {
// Extend current subarray or restart from nums[i]
currMax = Math.max(nums[i], currMax + nums[i]);
maxSoFar = Math.max(maxSoFar, currMax);
}
return maxSoFar; // O(n) time, O(1) space