Stop Memorizing Kadane’s Algorithm. Start Thinking Like It.

Most tutorials teach you the code. This one teaches you the thought.

Every DSA learner hits the same wall with Kadane’s algorithm. You watch a video, copy the five-line solution, and feel like you’ve got it — until a slightly twisted variant shows up and you’re completely lost.

That’s because most resources teach Kadane’s algorithm as a recipe. The real insight is that it’s a thinking pattern. Once you see it that way, you won’t just solve the classic maximum subarray problem — you’ll be able to adapt it to minimum sums, maximum products, and beyond, without memorizing anything new.

Let’s dig in.

The Problem Family Kadane’s Solves

Kadane’s algorithm is built for one specific class of problems: contiguous subarray optimization. That includes:

• Maximum sum subarray
• Minimum sum subarray
• Maximum product subarray
• Minimum product subarray

The common thread? You’re given an array (usually with a mix of positive and negative elements), and you need to find a contiguous subarray — a slice — that is “best” by some metric.

Why the Obvious Approach Fails

Your first instinct might be to try a sliding window. After all, it’s a subarray problem. But sliding window relies on a key assumption: adding elements to the window monotonically changes the result. Add a positive number → sum increases. Remove an element → sum decreases.

That breaks down the moment you introduce negative numbers. A negative element might drag your sum down temporarily, but a large positive right after it could make extending through that negative the right call. There’s no clean “expand or shrink” logic anymore.

Kadane’s sidesteps this entirely with a different question asked at every single index.

The Core Question Kadane’s Asks

At every index i, Kadane's algorithm asks:

Is it better to extend the best subarray that ended just before me, or to start fresh right here?

That’s it. Two choices, evaluated at every step:

1. Extend: Take the best subarray ending at i-1 and include A[i]
2. Start fresh: Begin a new subarray at i itself

For the maximum sum problem, you pick whichever is larger:

bestEnding[i] = max(bestEnding[i-1] + A[i], A[i])

And you track a running global maximum alongside it.

Walking Through an Example

Let’s run through [-2, 1, 2, -4, 5] step by step.

Index A[i] Extend (prev + A[i]) Start Fresh (A[i]) bestEnding[i] Global Max 0 -2 — -2 -2 -2 1 1 -2 + 1 = -1 1 1 1 2 2 1 + 2 = 3 2 3 3 3 -4 3 + (-4) = -1 -4 -1 3 4 5 -1 + 5 = 4 5 5 5

At index 1, extending through the -2 gives -1, which is worse than just starting fresh at 1. So we start fresh. By the end, the global maximum is 5, which is the subarray [5] alone.

Minimum Sum? Same Pattern, One Change

If you want the minimum sum subarray instead, flip max to min everywhere:

bestEnding[i] = min(bestEnding[i-1] + A[i], A[i])

The underlying thought process is identical. You’re still asking: “should I extend or start fresh?” — just now you’re choosing the option that gives the smaller value.

This is the point where the thought pattern pays off. You didn’t need to learn a new algorithm. You just adapted the one decision to a different goal.

The Tricky One: Maximum Product Subarray

Products introduce a wrinkle that sums don’t have: negatives flip signs.

Consider [-2, -4]. Individually, both are negative. But their product is 8. A large negative minimum can become a large positive maximum the moment it gets multiplied by another negative.

This means at every index, three candidates now exist — not two:

1. A[i] alone (start fresh)
2. maxEnding[i-1] × A[i] (extend the current maximum)
3. minEnding[i-1] × A[i] (extend the current minimum — it might flip to a big positive!)

So you track two arrays simultaneously:

maxEnding[i] = max(A[i], maxEnding[i-1] × A[i], minEnding[i-1] × A[i])
minEnding[i] = min(A[i], maxEnding[i-1] × A[i], minEnding[i-1] × A[i])

The final answer is the maximum across all maxEnding[i] values.

The thought pattern is the same. The only change is that you’re now tracking two “best endings” per index — because of how multiplication behaves with negatives.

The Pattern in Summary

Problem Track Update Rule Answer Max Sum Subarray bestEnding[i] max(prev + A[i], A[i]) max of all bestEnding Min Sum Subarray bestEnding[i] min(prev + A[i], A[i]) min of all bestEnding Max Product Subarray maxEnding[i], minEnding[i] Three-way max and min max of all maxEnding

The Mindset Shift That Makes This Click

The reason Kadane’s feels hard at first is that it’s usually taught backwards — code first, intuition never.

The actual insight is simple: you’re computing the best subarray ending at every index, independently. Once you have that for every index, the answer is just a scan over those best values.

At each index, you make a local choice — extend or start fresh. You pick based on what’s better right now, for this version of the problem. The global answer accumulates naturally.

That’s it. No magic. Just one honest question asked n times.

Closing Thought

The next time you face a subarray optimization problem, don’t reach for a memorized template. Ask yourself:

What is the best subarray that can end at index i? Should I extend the previous one, or begin again?

Answer that for every index, and you’ve already solved the problem.

Kadane’s algorithm isn’t a five-line trick. It’s a way of thinking about local decisions that compound into a global optimum. Understand that, and a whole family of problems becomes approachable — with or without looking up the code.

If this clicked for you, try implementing the maximum product subarray variant from scratch without referencing any code. If you can reason through the three choices at each step, you’ve truly internalized Kadane’s pattern.