How Kadane’s algorithm finds the maximum subarray in one pass

Give an interviewer the array [-2, 1, -3, 4, -1, 2, 1, -5, 4] and ask for the contiguous slice with the largest sum, and the answer is 6, coming from [4, -1, 2, 1]. This is LeetCode 53, and it shows up as the warmup on more phone screens than almost any other array problem. Interviewers like it for a simple reason. The brute force is obvious, the optimal is a two-line loop, and the gap between them is a real idea rather than a trick you either memorized or didn’t.

That idea is Kadane’s algorithm. Once you see it, it feels almost too small to have a name.

The obvious solution, and why it’s slow

The first thing most people reach for is checking every subarray. Pick a start index, pick an end index, sum the slice, keep the best. If you recompute the sum from scratch each time that’s O(n³), and it drops to O(n²) the moment you keep a running total as you extend the end pointer.

def max_subarray_bruteforce(nums):
    best = nums[0]
    for i in range(len(nums)):
        running = 0
        for j in range(i, len(nums)):
            running += nums[j]
            best = max(best, running)
    return best

For a few thousand elements this is fine. But LeetCode gives you inputs up to 10^5 elements, where the O(n²) version does on the order of 10^10 operations and times out. So the actual question behind the problem is whether you can get to linear time. That’s where the interesting part starts.

The single decision Kadane’s algorithm makes

Walk left to right and keep one number: the largest sum of any subarray that ends at the current position. Call it current. When you step to the next element you have exactly one choice. Either you extend the subarray you already had, or you throw it away and start fresh at this element.

You extend when the sum you’re carrying is worth keeping. You start over when it isn’t. Concretely, the running sum ending here is max(nums[i], current + nums[i]). If current was negative, adding it only drags nums[i] down, so you drop it and the subarray restarts at i. That’s the whole insight: a negative prefix can never help a later element, so the instant your running total goes negative you abandon it.

def max_subarray(nums):
    current = best = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

One pass, O(n) time, O(1) space. current tracks the best subarray ending at the position you’re looking at, and best remembers the best you’ve seen anywhere. Those two variables answer two different questions, and conflating them is the most common bug I watch people write when they code this under pressure.

The all-negative array that catches people

The input that catches people is [-3, -1, -2]. The correct maximum subarray sum is -1, because the problem asks for a non-empty contiguous slice and the least-bad single element is -1. Anyone who initializes their best to 0 returns 0, which corresponds to the empty subarray the problem never allowed.

That’s why best starts at nums[0], not at zero. It’s a small thing, and it’s exactly the kind of small thing an interviewer plants a test case for. If your first line is best = 0, expect the follow-up array to be all negative. Some interviewers deliberately change the problem to allow an empty subarray, in which case 0 becomes correct and you clamp best at 0. Ask which version they want before you write the base case. It signals you noticed the edge instead of stumbling into it.

Returning the subarray itself

Plenty of interviewers push past the number and ask for the actual indices. Same loop, a little bookkeeping. Track where the current run started, and whenever current resets to nums[i], that’s a new start. When best improves, record the window.

def max_subarray_indices(nums):
    current = best = nums[0]
    start = best_lo = best_hi = 0
    for i in range(1, len(nums)):
        if nums[i] > current + nums[i]:
            current = nums[i]
            start = i
        else:
            current += nums[i]
        if current > best:
            best = current
            best_lo, best_hi = start, i
    return best, (best_lo, best_hi)

The subtle part is updating best_lo only when best actually improves, and pinning start to the moment the run restarts. Get those two right and the window falls out for free. If you want a specific tie-break, say the earliest or the shortest window when several share the same sum, that’s worth saying out loud so the interviewer knows you’re aware there’s a choice to make.

Greedy or dynamic programming

Interviewers at the more theory-leaning shops sometimes ask you to classify it, and the answer is both, depending on how you frame it. Read as dynamic programming, define dp[i] as the largest subarray sum ending at index i. The recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i]), and the answer is the maximum over the whole dp array. Kadane’s is that exact recurrence with the table collapsed to a single variable, because dp[i] only ever looks back at dp[i-1]. The greedy read is the reset rule: locally drop any prefix that has turned negative. Both describe the same loop. Showing the dp array and then collapsing it to O(1) space is usually the moment the interviewer nods and moves on.

The follow-ups worth rehearsing

Once you have the base version, interviewers reach for a nearby variant to see whether you understood the mechanism or pattern-matched the code. A few come up often enough to prepare for.

Problem	LeetCode #	The twist vs. plain Kadane	Time / Space
Maximum Subarray	53	Baseline: track the best sum ending at the current index	O(n) / O(1)
Maximum Product Subarray	152	Negatives flip sign, so carry both the max and the min product ending here	O(n) / O(1)
Maximum Sum Circular Subarray	918	Answer is either plain Kadane or total sum minus the minimum subarray, with the all-negative case guarded	O(n) / O(1)
Maximum Subarray, divide and conquer	53	Split the array, solve each half, and check the best subarray crossing the midpoint	O(n log n) / O(log n)

The product variant (152) is the one people botch. Multiplying by a negative turns your largest running product into the smallest and the smallest into the largest, so a single current isn’t enough. You carry a running max and a running min, and at each step you recompute both from nums[i], max_so_far * nums[i], and min_so_far * nums[i]. Skip the min and the array [-2, 3, -4] only reaches its answer of 24 by accident, because the min of -6 becomes the max the moment you multiply it by -4.

The circular version (918) has a clean trick. The best circular subarray either sits in the middle like an ordinary one, or it wraps around the ends, which means it excludes a contiguous middle chunk. The chunk you drop to maximize the wrap is the minimum-sum subarray, so the wrapped answer is total_sum - min_subarray. Take the larger of plain Kadane and that, with one caveat: if every element is negative, total_sum - min_subarray comes out to 0 because you excluded the entire array, which isn’t a valid non-empty answer, so you fall back to the plain Kadane result.

Divide and conquer, splitting the array, solving each half, then checking the best subarray that straddles the midpoint, is the answer to “can you do it another way.” It’s O(n log n), strictly worse than Kadane, but worth being able to sketch because it generalizes to range queries where you need the maximum subarray of an arbitrary sub-range. Plain Kadane can’t answer that without recomputing from scratch, and a segment tree built on the divide-and-conquer merge can.

What keeps this problem in rotation is that the linear solution isn’t a lookup-table fact. It’s a decision you can re-derive at the whiteboard from one observation about negative prefixes, and everything downstream, the indices, the product twist, the circular wrap, is that same observation seen from a different angle. Interviewers know it, which is why they keep the base problem easy and spend the real time on where you take it next.