Kadane’s Algorithm Explained: The Smart Way to Find Max Subarray

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;

}

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 numbers
• No extra space required

For More: https://www.quipoin.com/tutorial/data-structure-with-java/kadane-algorithm