How to Learn Kadane’s Algorithm: Maximum Subarrays, Running Bests, Dynamic-Programming Invariants and One-Pass Optimisation

What if the best part of a long sequence can be found without checking every possible part? Kadane’s Algorithm is a compact answer to the maximum-subarray problem: among all contiguous blocks of numbers, find the one with the largest sum. Its code can fit on a few lines. Understanding why those lines are correct is the real lesson.

This Learning Hall article develops Kadane’s Algorithm from visible tracing to invariant-based reasoning, robust implementation and professional extensions. It complements the broader Dynamic Programming learning article; it does not replace that wider job.

Quick Read

The problem asks for the maximum-sum contiguous subarray.
Kadane’s central state is the best non-empty subarray ending exactly at the current position.
At each element, either extend the previous subarray or start again here.
A second variable remembers the best result seen anywhere so far.
The classic algorithm runs in O(n) time with O(1) auxiliary state when only the value is required.
Professional implementations must define all-negative behaviour, empty-input semantics, tie-breaking, index recovery, numeric types and invalid values.

1. Beginner Level: What Is a Maximum Subarray?

Take the sequence:

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

A subarray is a contiguous slice. You may choose [4, -1, 2, 1], but you may not skip the -1 and call [4, 2, 1] a subarray. The chosen slice sums to 6, which is the maximum for this example.

The first useful learning move is not to code. Trace possible slices by hand. Ask what makes a prefix worth carrying forward. If a running sum has become harmful enough that starting fresh at the next number is better, the old prefix has lost its claim on the future.

2. From Brute Force to the One-Pass Idea

A direct approach can choose every start position and every end position and compute each sum. With reused prefix sums this can be reduced to O(n²) candidate intervals, but it still considers far more possibilities than necessary.

Kadane’s insight is local but not greedy in the careless sense. When we arrive at value x, the best subarray that ends here has only two possible forms:

start a new subarray containing only x; or
extend the best subarray that ended at the previous position by adding x.

That gives the recurrence:

end_here = max(x, end_here + x)
best = max(best, end_here)

Those two lines are useful only after their meanings are precise.

3. The Invariant That Makes Kadane Correct

end_here means: the maximum sum of any non-empty subarray that ends exactly at the current index. It is not the best sum anywhere in the array. It has an endpoint obligation.

best means: the maximum sum of any non-empty subarray seen in the processed prefix.

Suppose the invariant is true before processing x. Any subarray ending at x either begins at x or includes the previous position. If it includes the previous position, using anything worse than the best previous ending would never improve the result. Therefore max(x, end_here + x) considers every structurally relevant possibility. Updating best then preserves the best answer over the entire prefix.

This is dynamic programming compressed into constant state. We do not store the whole DP table because the next state needs only the previous ending value and the global best.

4. Trace Before You Code

For the example sequence, write two columns after every element: end_here and best.

x      end_here   best
-2        -2       -2
 1         1        1
-3        -2        1
 4         4        4
-1         3        4
 2         5        5
 1         6        6
-5         1        6
 4         5        6

Notice the restart at 4. Extending the previous ending sum of -2 would produce 2, while starting at 4 produces 4. The algorithm does not restart because negative numbers are forbidden; it restarts because the invariant proves the previous prefix is no longer useful to an optimal subarray ending here.

5. A Correct Non-Empty Implementation

def kadane(values):
    if not values:
        raise ValueError("values must be non-empty")

    end_here = values[0]
    best = values[0]

    for x in values[1:]:
        end_here = max(x, end_here + x)
        best = max(best, end_here)

    return best

Initialising from the first element is not cosmetic. It gives correct semantics for an all-negative sequence such as [-8, -3, -6], whose best non-empty subarray is [-3]. Initialising best to zero would silently change the problem into a version that permits the empty subarray.

6. Empty Versus Non-Empty Is a Specification Decision

There are two legitimate problem definitions. In the non-empty version, at least one element must be selected. In an empty-allowed version, choosing no elements can produce sum zero. They give different answers on all-negative input.

Strong algorithm engineering begins by fixing this contract before implementation. A test suite should contain an all-negative case precisely because it exposes which definition the code is actually solving.

7. Recovering the Start and End Indices

Production tasks often need the interval, not only its sum. Track where the current candidate began. Whenever starting at x is better than extending, reset the tentative start index. Whenever best improves, snapshot both endpoints.

def maximum_subarray(values):
    if not values:
        raise ValueError("values must be non-empty")

    end_here = best = values[0]
    current_start = 0
    best_start = best_end = 0

    for i in range(1, len(values)):
        x = values[i]

        if x > end_here + x:
            end_here = x
            current_start = i
        else:
            end_here += x

        if end_here > best:
            best = end_here
            best_start = current_start
            best_end = i

    return best, best_start, best_end

The use of > instead of >= defines one tie policy. Equal-sum solutions can have different starts or lengths, so professional code should document whether it prefers the earliest, latest, shortest or longest optimal interval.

8. Why Kadane Is Not a Sliding-Window Algorithm

Students sometimes group Kadane with two-pointer or sliding-window methods because all can make a single left-to-right pass. The reasoning is different. A typical sliding window maintains a feasibility condition while boundaries move. Kadane maintains an optimal-value invariant for an endpoint.

This distinction becomes important in a real sliding stream where old elements expire. Standard Kadane state cannot simply “subtract the expired element” and remain correct, because the optimal historical subarray may depend on structure that has already been discarded. Dynamic or sliding-window variants require additional machinery.

9. Complexity: Why the Improvement Is Real

Each element is processed once and triggers constant work. The running time is therefore O(n). If only the maximum sum is returned, auxiliary state is O(1). Index recovery still needs only constant extra state beyond the input.

The deeper improvement is not merely “one loop instead of two.” It comes from proving that the whole history can be represented by a tiny sufficient state. That is a recurring professional skill in dynamic programming: identify what the future actually needs from the past.

10. Failure Cases Worth Testing

One element: [7] and [-7].
All negative: catches accidental empty-subarray semantics.
All positive: the whole array should win.
Zeros: exposes tie-breaking decisions.
Repeated equal optima: tests which interval is returned.
Very large integers: languages with fixed-width arithmetic can overflow.
Floating point: NaN and infinities require an explicit policy.
Empty input: return a sentinel, zero, None or raise—choose deliberately.

11. Test the Invariant, Not Only the Final Answer

A useful debugging exercise compares end_here after each index against a slow reference that enumerates every subarray ending at that index. This catches errors earlier than checking only the final result.

For randomized testing, generate small arrays, compute the answer by an obvious O(n²) reference implementation, and compare it with Kadane. A slow oracle is extremely valuable when the optimized algorithm is compact enough to look correct even when one boundary condition is wrong.

12. Extending the Idea to Two Dimensions

For a matrix, the analogous problem asks for the maximum-sum contiguous rectangle. One classical approach chooses pairs of row boundaries, compresses the values between those rows into column sums, and runs the one-dimensional maximum-subarray algorithm on that compressed vector.

The lesson is more important than memorising the exact complexity: a trusted one-dimensional primitive can become the inner engine of a higher-dimensional algorithm after a representation change.

13. Professional Data Questions

In finance, telemetry, scientific measurements or performance traces, “maximum contiguous gain” can sound meaningful while the input semantics are not. Are values increments or absolute levels? Are missing samples encoded as zero? Can a gap be crossed? Are observations equally spaced? Is the receiver looking for the largest absolute sum, the largest average, a fixed-duration interval or a statistically significant change?

Kadane solves one exact mathematical problem. Good engineering verifies that the real question is that problem before celebrating an O(n) solution to the wrong objective.

14. A Learning Method That Builds Transfer

Programming-education research supports moving learners from worked code toward independent construction rather than dropping novices directly into a blank editor. For Kadane, a productive sequence is: predict the two state values on a trace, run a known implementation, investigate why a restart happens, modify it to return indices, then rebuild it without the example visible.

Faded worked examples are useful here. First provide the full trace. Next remove selected state updates. Then ask the learner to complete the recurrence. Finally ask for a fresh implementation and a proof sketch. The objective is not merely remembering two lines of Python; it is retrieving the invariant that regenerates those lines.

15. Beginner-to-Professional Progression

Beginner: identify contiguous versus non-contiguous selections and trace end_here and best by hand.
Intermediate: implement the non-empty version, recover indices and explain the invariant in plain language.
Advanced: prove correctness by induction, define tie semantics, build a brute-force oracle and test randomized inputs.
Professional: handle numeric and missing-data policies, embed the routine inside larger pipelines, benchmark realistic workloads and recognise when the real problem is a windowed, constrained or higher-dimensional variant.

16. Practice Problems

Trace Kadane on [-5, -2, -9, -1]. Explain why zero is not the answer under non-empty semantics.
Modify the index-returning implementation to prefer the shortest optimal interval.
Write an O(n²) reference solver and property-test it against Kadane on thousands of small random arrays.
Return both the maximum sum and the number of optimal intervals.
Adapt the method to maximum product and explain why zeros and negative values make the state more complicated.
Design a matrix maximum-rectangle solver that uses Kadane as an inner routine.
Explain why deleting an expired leftmost item from a stream cannot be handled by simply subtracting it from end_here.

17. Sources and Further Reading

Final idea: Kadane’s Algorithm is memorable because it is short, but valuable because it teaches state compression. The professional question is not “Can I remember the two assignments?” It is “Can I explain exactly what information the future needs from the past, prove that nothing else matters, and rebuild the algorithm from that invariant?”

Small Group Tutorials