Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to Kadane's Algorithm

Medium5 min readdsakadane-s-algorithm

Introduction to Kadane's Algorithm

Kadane's algorithm is the canonical answer to one of the most-asked interview questions in existence: what is the largest sum you can get from a contiguous subarray? It solves that in a single O(n) pass with O(1) memory, and the reasoning behind it - a tiny running-state decision made at every element - generalizes into an entire family of "best contiguous run" problems. If sliding window (Module 12) is about maintaining an explicit [left, right] range, Kadane is about something subtler: never tracking the window's boundaries at all, just the best run ending right here.

This introduction lays out the core insight, the running-state recurrence, the relationship to prefix sums, and the variants - products, circular arrays, deletions, turbulence - that make up the rest of the module.

The One Decision Kadane Makes

Walk the array left to right. At each element, ask a single question about the best contiguous subarray that ends at this exact position:

"Should I extend the best run ending at the previous element, or start fresh from here?"

You start fresh exactly when the previous best run was a liability - when its sum was negative, dragging you down. Otherwise you extend. Formally, letting best[i] be the maximum sum of a subarray ending at index i:

best[i] = max(nums[i], best[i-1] + nums[i])

The global answer is max(best[i]) over all i. Because best[i] depends only on best[i-1], you don't need an array - a single running variable suffices, giving O(1) space.

graph TD
    A["At element nums[i]"] --> B{"best so far ending at i-1<br/>positive?"}
    B -->|Yes| C["Extend:<br/>best = best + nums[i]"]
    B -->|No| D["Start fresh:<br/>best = nums[i]"]
    C --> E["answer = max(answer, best)"]
    D --> E
    E --> F["move to i+1"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This diagram shows the single decision Kadane makes at each element. If the best run ending at the previous position has a positive sum, we extend it by adding the current element. Otherwise we start a fresh run at the current element. After deciding, we update the global answer with the running best.

Why "Ending Here" Is the Magic

The trick that makes Kadane work is reframing the problem. "Find the max-sum subarray anywhere" sounds like it requires considering all O(n²) subarrays. But every subarray ends somewhere. So if you can compute, for each position, the best subarray that ends exactly there, then the overall best is simply the largest of those n values.

And the best subarray ending at i has a beautiful recursive structure: it's either just nums[i] alone, or it's nums[i] glued onto the best subarray ending at i-1. There's no third option - anything ending at i must include nums[i], and whatever precedes it is some subarray ending at i-1 (or nothing). That's the whole algorithm.

The Running-State Pattern

Kadane is the archetype of a broader pattern: carry a small running state, make a local decision at each element, update a global answer. This pattern recurs across the module with different state:

• Maximum Subarray (13.2): state is the best sum ending here.
• Maximum Product Subarray (13.5): state is two values - the max and min product ending here - because a negative flips min into max.
• Maximum Sum Circular Subarray (13.4): run Kadane twice - once for the max, once for the min (to handle wraparound via the complement).
• Maximum Subarray Sum with One Deletion (13.7): state tracks the best run with zero deletions and with one deletion used.
• Longest Turbulent Subarray (13.6): state tracks run lengths under an alternating-comparison rule.

The lesson the module teaches: once you see a "best contiguous run" problem, ask what minimal state, carried element to element, lets me make the local decision? That state is the heart of every Kadane variant.

Relationship to Prefix Sums

Kadane is deeply connected to prefix sums (Module 11). The sum of a subarray (i, j] is P[j] - P[i], where P is the prefix-sum array. Maximizing that over all i < j means, for each j, subtracting the minimum prefix seen so far:

maxSubarray = max over j of ( P[j] - min(P[0..j-1]) )

That's literally Kadane in prefix-sum clothing: "best subarray ending at j" equals "current prefix minus the smallest earlier prefix." Both views give O(n); the running-variable form is just leaner. Keeping this duality in mind helps when a variant is easier to reason about in one frame than the other - Maximum Sum Circular Subarray, for instance, leans on the prefix/total-sum view.

graph LR
    A["Kadane view:<br/>best run ending here"] --- B["same answer"]
    B --- C["Prefix view:<br/>P[j] - min prefix before j"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This diagram shows the duality between Kadane's running-state view and the prefix-sum view. Kadane tracks the best run ending at each position; the prefix view computes the current prefix sum minus the smallest earlier prefix. Both produce the same maximum-subarray answer.

When to Reach for Kadane

Kadane fits when all of these hold:

• The answer is a contiguous subarray (not a subsequence - gappy selections need DP).
• You're optimizing an aggregate (sum, product, or a run length under some rule) over those subarrays.
• The aggregate can be maintained by a local decision at each element using a constant amount of carried state.

The classic signal phrases: "maximum/minimum sum subarray," "largest product of a contiguous run," "best contiguous … such that …." If the problem adds a twist - wraparound, one allowed deletion, alternating signs - it's usually still Kadane, just with richer state.

What Kadane Is Not For

• Non-contiguous selections. "Maximum sum of a subsequence" is trivial for positives (take them all) or a different DP for constraints - not Kadane.
• Problems needing the actual indices by default. Kadane gives the value in O(1) space; recovering the boundaries needs a little extra bookkeeping (track where the current run started).
• Conditions that aren't expressible as a local running-state update. If deciding the best run ending here requires re-examining the whole prefix, Kadane's O(1) update breaks.

What This Module Covers

The module is organized by how far each problem stretches the core idea:

• Classic Kadane (13.2–13.3): Maximum Subarray itself, then Best Sightseeing Pair - a problem that isn't obviously Kadane until you reframe it as "carry the best left-contribution forward."
• Kadane Variants (13.4–13.6): Maximum Sum Circular Subarray (wraparound via the total-minus-min-subarray trick), Maximum Product Subarray (track max and min), and Longest Turbulent Subarray (run lengths under alternating comparisons).
• Kadane with Constraints (13.7–13.8): Maximum Subarray Sum with One Deletion (a two-state Kadane), and Maximum Absolute Sum of Any Subarray (max of "max subarray" and "−min subarray").

Each problem walks the brute-force → Kadane arc, so you see why the running-state decision is correct, not just that it works. By the end, the recurrence best = max(nums[i], best + nums[i]) and its variations should be reflexive.

Let's begin with the problem that defines the technique: Maximum Subarray, where the single running-best decision is laid bare.

Back to DSA Mastery - Interview Prep, End to End