Finding the maximum subarray sum sounds simple…
Until you try brute force:
Check all subarrays → O(n²)
But what if you could solve it in O(n)?
That’s exactly what Kadane’s Algorithm does.
Core Idea
At every index, you make a decision:
Start a new subarray
OR extend the previous one
Whichever gives a larger sum.
Implementation
public static int maxSubarraySum(int[] arr) {
int maxSoFar = arr[0];
int maxEndingHere = arr[0];
for (int i = 1; i < arr.length; i++) { maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]); maxSoFar = Math.max(maxSoFar, maxEndingHere); }
return maxSoFar;
Enter fullscreen mode
Exit fullscreen mode
}
Example
Array:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
Best subarray:
[4, -1, 2, 1] → sum = 6
Why It Works
Negative sum hurts future results
So we drop it and start fresh
Positive sum helps → we extend it
The Real Insight
Kadane is about making a local decision
that leads to a global optimum
Key Insights
Tracks current max and global max
Works with negative…