Kadane's Algorithm: The Five-Line Trick Every Developer Should Know

2026-04-17
algorithms dynamic-programming arrays patterns kadane

Some algorithms are clever. A few are beautiful. Kadane’s algorithm is in the rare category of being both — and it’s short enough that you can memorize it over coffee. If you’ve ever needed to find the “best contiguous chunk” of anything — the best window of stock returns, the worst burst of errors, the highest-scoring region in a sequence — you’ve already needed Kadane’s. Most developers just don’t know it has a name.

The Problem

Given an array of numbers, some positive and some negative, find the contiguous subarray with the largest sum.

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

The best subarray here is [4, -1, 2, 1] with a sum of 6. Easy to eyeball for nine numbers. Much harder when the array has a million.

The naive approach is to try every possible subarray: pick a start, pick an end, sum the range, keep the best. That’s O(n²) at best and O(n³) if you’re not careful. On a million-element array, O(n²) means a trillion operations. Not going to happen.

Kadane’s algorithm solves it in O(n) time and O(1) space. One pass, one running sum, one best-so-far. In 1984, Jay Kadane wrote it on a whiteboard at Carnegie Mellon in under a minute. It’s been the canonical answer ever since.

The Algorithm

Here’s the whole thing in Go:

func maxSubArray(nums []int) int {
    best, current := nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        if current+nums[i] < nums[i] {
            current = nums[i]
        } else {
            current = current + nums[i]
        }
        if current > best {
            best = current
        }
    }
    return best
}

Five meaningful lines. That’s the algorithm.

The Insight

The magic is in one question Kadane asks at every index:

Is the running sum still helping me, or should I start fresh here?

If the running sum has gone negative, it’s dragging down anything that comes after it. Throwing it away and starting from the current element is always better. If it’s still positive, you extend it.

That’s it. That’s the whole idea. You make a local decision at each index — extend or reset — and the global maximum falls out naturally. Kadane’s is the smallest, cleanest example of dynamic programming you’ll ever see: one state (current), one transition, one pass.

It also happens to be a perfect example of why DP and greedy algorithms often look so similar. Kadane’s can be taught either way, which is part of what makes it such a useful thinking tool.

Why It Matters

Kadane’s deserves a spot in every working developer’s mental toolkit for four reasons.

1. It’s the gateway drug to dynamic programming. If you’ve ever bounced off DP because the textbook examples felt abstract, Kadane’s is the antidote. One variable, one decision, one pass. After you understand it, harder DP problems start making sense because you’ve seen the shape of the thinking at its smallest scale.

2. It’s one of the cleanest O(n²) → O(n) wins in the canon. Seeing how a quadratic brute force collapses into a linear pass is the kind of thing that rewires how you look at loops. Once you’ve seen it, you start spotting similar collapses everywhere in your own code.

3. It teaches the “local decision, global optimum” mindset. A lot of real engineering problems are secretly about making a cheap local choice at every step and trusting that the global answer emerges. Kadane’s is the purest form of that pattern.

4. It generalizes. Once you know Kadane’s, you can extend it to 2D (maximum-sum submatrix in a grid), to circular arrays, to “at most K negatives,” to “max product subarray,” and to problems that aren’t about numbers at all. It’s a pattern, not a trick.

How Developers Actually Use Kadane’s

This is where it stops being a LeetCode problem and starts being a tool. Kadane’s — or a direct descendant of it — shows up constantly in production code, often without anyone calling it by name:

In all of these, the interesting part isn’t typing out the algorithm. It’s recognizing that the problem in front of you — framed in business language — is secretly a maximum subarray problem.

The Pattern to Internalize

Forget the code for a moment. The pattern is:

Running best with reset. Walk the sequence. Keep a running total. If the total stops helping you, throw it away and start again. Track the best total you’ve ever seen.

Any time you find yourself scanning a sequence and asking “what’s the best contiguous chunk?”, Kadane-style thinking is the right starting point. The exact code will vary — you might be maximizing, minimizing, tracking a product, or combining multiple signals — but the “extend or reset” decision is the same.

One small edge case worth remembering: if your array can be entirely negative, make sure your initial best starts at the first element, not at zero. Otherwise you’ll return 0 for [-3, -1, -4] when the correct answer is -1. The Go snippet above handles this correctly by initializing from nums[0].

The Takeaway

Five lines of code. Forty years old. Still one of the most quietly useful algorithms a working developer can have in their head. The next time you catch yourself writing a nested loop to find “the best stretch of something,” pause. There’s a very good chance Jay Kadane already solved it for you in 1984.

If you want to build the intuition for spotting these opportunities, Algos by Example organizes problems by pattern so you can see the same ideas recur across different contexts. Kadane’s is one of the smallest, but it’s also one of the most generalizable — well worth an afternoon of your time.

← Back to Blog