Menu

1 / 2

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

DEV Community·Quipoin·7 months ago
#Bddh0JMu
Reading 0:00
15s threshold

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…

Continue reading — create a free account

Join HashtagPLUS to read full articles, follow hashtags, vote, and join the conversation.