Kadane’s Pattern — Linear-Time Maximum Subarray
Use Kadane’s dynamic programming insight to find maximum subarray sums, track boundaries, and pivot to 2D variations.
Problem Statement
Given an array of integers, compute the contiguous subarray with the largest sum in O(n) time using Kadane’s algorithm.
Why This Problem Matters
- Kadane’s algorithm is the canonical example of reducing O(n²) brute force to O(n) via running state.
- Mastering it builds intuition for prefix sums, running bests, and dynamic programming transitions.
- Variations like circular arrays or tracking indices show up frequently in interviews.
Thought Process
Track current and global best
Current best either extends the previous subarray or starts fresh at the current number. Global best records the maximum seen so far.
Reset when prefix becomes harmful
If the running sum dips below zero, it can only hurt future sums—reset it to the current value.
Optionally store boundaries
Track start/end indices when you improve the global best so you can return the subarray, not just the sum.
Step-by-Step Reasoning
- Initialise currentSum = globalSum = nums[0].
- Iterate from index 1 onward.
- currentSum = Math.max(nums[i], currentSum + nums[i]).
- Update globalSum = Math.max(globalSum, currentSum).
Dry Run
Array [-2, 1, -3, 4, -1, 2, 1, -5, 4]
currentSum resets at 4, then grows to 6, then 7. globalSum = 6 and final answer is subarray [4, -1, 2, 1].
Array [5, -1, 5]
currentSum never dips below zero; globalSum ends up at 9 using the entire array.
Complexity Analysis
Time
O(n)
Space
O(1)
Why
Each element is processed once and only constant extra variables are maintained.
Annotated Solution
public class Kadane {
public static int maxSubArray(int[] nums) {
int current = nums[0];
int best = nums[0];
for (int i = 1; i < nums.length; i += 1) {
current = Math.max(nums[i], current + nums[i]);
best = Math.max(best, current);
}
return best;
}
}The recurrence embraces the idea that every prefix either helps or hurts the future sum. Extending only when helpful keeps the result optimal.
Common Pitfalls
- Resetting currentSum incorrectly (e.g., to 0 instead of nums[i]) fails when all numbers are negative.
- Forgetting to initialise with nums[0] can break arrays of length 1.
- Mixing up inclusive/exclusive indices when returning the subarray.
Follow-Up Questions
- Adapt to 2D maximum submatrix sum by fixing row pairs and running Kadane on column sums.
- Modify for circular arrays where the answer may wrap around the end.
- Track start/end indices alongside sums so you can return the window.