Max Subarray Sum
Walk through the array keeping a running sum. If the running sum goes negative, reset to 0 (start fresh). Track the maximum running sum seen — that's your answer. Simple, O(n), and beautiful.
How It Works
Kadane's algorithm finds the maximum-sum contiguous subarray in a single pass. At each index it answers one local question: is it better to extend the best subarray ending at the previous element, or to start fresh here? Concretely, currentSum = max(nums[i], currentSum + nums[i]), and a global maximum tracks the best value ever seen.
The insight is that a negative running sum can never help any future subarray, so it is discarded the moment it drags below the current element alone. This dynamic-programming view — best subarray ending at i depends only on the answer at i−1 — replaces the O(n²) enumeration of all subarrays with O(n) time and O(1) space.
Step-by-Step Visualization
Code
static int maxSubarraySum(int[] nums) {
int currentSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
// Key decision: extend or start fresh?
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
// Example: maxSubarraySum(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4})
// Answer: 6 (subarray [4, -1, 2, 1])Tips & Gotchas
Practice Problems
- 1Maximum Subarray
- 2Best Time to Buy and Sell Stock
- 3Maximum Sum Circular Subarray
- 4Longest Turbulent Subarray
About the Kadane's / Subarray Pattern
At each position, decide: should I extend the previous subarray, or start fresh here? Track the running sum and the global maximum. This elegant approach finds the maximum subarray sum in O(n).
When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.
Common Array Interview Problems
- Two Sum
- Best Time to Buy & Sell Stock
- Maximum Subarray
- Merge Intervals
- Product of Array Except Self
- Container With Most Water
Frequently Asked Questions
Does Kadane's algorithm work when every element is negative?
Yes, provided you take max(nums[i], currentSum + nums[i]) rather than resetting the running sum to zero. The first formulation naturally returns the largest single element; the reset-to-zero variant incorrectly reports 0, which corresponds to an empty subarray.
How is Best Time to Buy and Sell Stock a Kadane problem?
Transform prices into an array of day-to-day differences; the best single buy-sell profit is exactly the maximum-sum subarray of those differences. Running Kadane's on the deltas yields the answer in O(n) with no extra array needed.
How do I recover the actual subarray, not just its sum?
Track a tentative start index that resets whenever you start fresh, and record start and end whenever the global maximum improves. This adds O(1) bookkeeping without changing the single-pass structure.