Kadane's Algorithm Explained: Maximum Subarray in O(n)

Maximum subarray is the question that looks like it needs a clever data structure and needs two variables. What makes it worth studying is not the answer — it is that the argument for why the answer is correct is three sentences long, and reciting those three sentences is the entire interview.

The problem it solves

Given an array that mixes positive and negative numbers, find the contiguous stretch with the largest sum. Best run of trading days, warmest span of a season, highest-scoring window of a match.

There are n(n+1)/2 subarrays, so checking them all is O(n²) even when the sum is carried incrementally, and O(n³) if it is not. That is the baseline worth naming out loud before improving on it.

The intuition

Stop thinking about subarrays and think about endings. Every subarray ends somewhere. So ask a smaller question at each index:

What is the best sum of any subarray that ends exactly here?

That has only two possible answers. Either the best stretch ending here extends the best stretch ending at the previous index, or it starts fresh at the current element. There is no third option, because a subarray ending at index i either includes index i-1 or it does not.

And choosing between those two takes no lookahead at all. If the running sum you would carry forward is negative, then adding the current element to it is strictly worse than taking the current element alone. The past is not merely unhelpful, it is a liability, and you drop it.

That is the whole algorithm: current = max(x, current + x). The global answer is the largest value current ever reached, which is a separate variable because the best stretch does not necessarily end at the last index.

This is dynamic programming with the table thrown away. The state is "best sum ending at i", it depends only on "best sum ending at i-1", so you keep a number instead of an array — which is worth saying explicitly, because interviewers often ask for the DP framing after you give the clever-looking two-liner.

Watch it run

Two numbers move through the array: the streak ending at the current element, and the best the streak has ever been. Watch the restart happen — the moment the running total is worth less than the element in front of it.

Notice that the best value freezes for long stretches while the current value thrashes around. Those are different questions, which is why they are different variables.

The code

def max_subarray(nums):
    """The best sum, plus the slice that produced it."""
    best = current = nums[0]
    start = best_start = best_end = 0
    for i in range(1, len(nums)):
        x = nums[i]
        if current + x < x:            # the carry-in is a liability: drop it
            current, start = x, i
        else:
            current += x
        if current > best:
            best, best_start, best_end = current, start, i
    return best, nums[best_start:best_end + 1]

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # (6, [4, -1, 2, 1])
print(max_subarray([-8, -3, -6]))                      # (-3, [-3])
print(max_subarray([-1, 5, -1, 5, -1]))                # (9, [5, -1, 5])

The bare version of this is two lines inside the loop. Everything else here is the index bookkeeping, and it is worth writing because "what was the subarray" is the natural follow-up question and the point where an unprepared candidate has to start over.

The rule for the indexes is small: start moves only on a restart, and the triple is copied into the best_* variables only when a new maximum is set. Do not update best_end outside that branch — a later, worse current would stretch the winning slice past where it actually ended.

The complexity

Time: O(n). One pass, a constant amount of work per element, no inner loop and no sorting.

Space: O(1). Two running values, plus three indexes if you want the slice back. The DP table that the recurrence implies is never allocated, because each state reads only its immediate predecessor.

That combination — linear time, constant space, one pass — is why this particular algorithm keeps being asked. It is the smallest complete demonstration that a O(n²) search space can collapse to O(n) when the subproblem is chosen well, and the choice of subproblem ("ending exactly here") is the part being tested.

Where it goes wrong

• Starting best at zero. Covered above; it is the single most common failure and it passes every test that happens to contain a positive number.
• Starting best at a sentinel like -1. Same bug wearing a disguise, and worse: it fails on [-8, -3, -6] by returning -1, a value that is not in the array and not the sum of anything.
• Empty input. nums[0] raises IndexError. Decide whether the contract allows an empty array and handle it in one line at the top rather than discovering it mid-explanation.
• Comparing best inside the wrong branch. The best update belongs after the current-value update, every iteration — not only on restarts, and not only on extensions.
• Confusing it with the maximum product subarray. That problem needs two running values, minimum as well as maximum, because a large negative multiplied by a negative becomes the new maximum. The additive intuition does not carry over, and assuming it does is a trap in the follow-up.
• Reaching for a sliding window instead. A window shrinks from the left when the sum gets too large, which only makes sense when the values are non-negative. With negatives there is no monotonic signal to shrink on. Kadane's restart is the correct form of that instinct.

How to say it in an interview

Lead with the subproblem, not the code:

"I will track the best subarray sum that ends at each index. That value is either the previous one extended by the current element, or the current element on its own — whichever is larger — because if the running sum is negative, carrying it forward can only hurt. I keep a separate global maximum, since the best stretch need not end at the last element. One pass, O(n) time, O(1) space. If the array is entirely negative the answer is the largest single element, so I initialise from nums[0] rather than from zero, and I will keep a start index so I can return the actual subarray."

That is the full answer, including both follow-ups, before either is asked.