Maximum Subarray: Kadane's Algorithm

You are given an integer array nums. Find the contiguous subarray (containing at least one element) which has the largest sum and return that sum.

This is LeetCode 53: Maximum Subarray, and it is one of the most frequently asked interview questions on the platform. The trick is an algorithm called Kadane's algorithm, which solves it in a single pass. Once you see the core idea, you will wonder how you ever thought this was hard.

The brute force approach

The most obvious approach is to check every possible subarray. For each starting index i, try every ending index j >= i, compute the sum, and track the maximum.

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

This works, but it is O(n^2). For an array with 100,000 elements, that is around 5 billion operations. Way too slow for LeetCode.

The problem is that we are doing a ton of redundant work. When we finish checking subarrays starting at index i, we throw away everything we learned and start over at index i + 1. There has to be a way to carry useful information forward.

The key insight: extend or restart

Here is the idea behind Kadane's algorithm. As you walk through the array, you maintain a running sum of the current subarray. At each new element, you face a simple decision:

1. Extend the current subarray by adding this element to the running sum.
2. Restart a brand new subarray starting at this element.

Which should you pick? Whichever gives a larger sum. In code, that is:

current_sum = max(nums[i], current_sum + nums[i])

Think about what this means. If current_sum has gone negative, then adding it to nums[i] would actually make things worse. You would be better off ditching the old subarray and starting fresh. But if current_sum is still positive (or zero), it is worth extending because it can only help.

That is the entire algorithm. One decision at each element. Track the best current_sum you have ever seen, and that is your answer.

Walking through it step by step

Let's trace through the classic example nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]. At each step we track current_sum (the best subarray ending here) and max_sum (the best we have seen overall). Green cells show the current subarray being tracked.

The answer is 6, from the subarray [4, -1, 2, 1].

Notice the critical moment at step 4. The running sum had dropped to -2, so when we hit the 4, restarting was better than extending. That decision is what makes Kadane's algorithm work. Without it, we would carry negative baggage forward and miss the optimal subarray.

The code

Here is the full implementation in Python:

def max_subarray(nums):
    current_sum = nums[0]
    max_sum = nums[0]

    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)

    return max_sum

Five lines of logic. Let's break it down:

1. Initialize both current_sum and max_sum to nums[0]. We need at least one element, so the first element is our starting point.
2. For each subsequent element, decide: is it better to extend the current subarray or restart here? That is the max(nums[i], current_sum + nums[i]) line.
3. After updating current_sum, check if this is the best subarray sum we have ever seen. If so, update max_sum.
4. Return max_sum at the end.

An alternative way to think about it

Some people find it easier to think of Kadane's algorithm as dynamic programming. Define dp[i] as the maximum subarray sum ending at index i. Then:

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

The answer is max(dp[0], dp[1], ..., dp[n-1]).

This is exactly what Kadane's algorithm computes, but instead of storing the entire dp array, we only keep the previous value (current_sum) and the running maximum (max_sum). It is the same space optimization trick you see in Climbing Stairs: when the recurrence only looks back one step, you only need one variable.

def max_subarray_dp(nums):
    dp = [0] * len(nums)
    dp[0] = nums[0]

    for i in range(1, len(nums)):
        dp[i] = max(nums[i], dp[i - 1] + nums[i])

    return max(dp)

This O(n) time, O(n) space version makes the DP structure explicit. Kadane's algorithm is just the O(1) space optimization of this.

Complexity analysis

Time: O(n). We visit each element exactly once. Each visit does O(1) work (a comparison and possibly an update). Total: O(n).

Space: O(1). Two variables (current_sum and max_sum), regardless of input size. No extra arrays, no hash maps.

This is optimal. You must look at every element at least once (the answer could depend on any of them), so O(n) time is the best possible. And O(1) space means zero overhead.

There is also a divide-and-conquer approach that runs in O(n log n), but Kadane's is simpler and faster, so it is the go-to solution in interviews.

Why Kadane's algorithm works

The correctness comes from a simple observation: the maximum subarray must end somewhere. If we can find the best subarray ending at every index, then the overall maximum is just the best among all of those.

At each index, the best subarray ending here either:

• Includes the previous element (extend), or
• Starts fresh at this element (restart)

There is no third option. And the choice between them is straightforward: if the previous best ending sum is positive, extending always helps. If it is negative, it would only drag us down.

This greedy-local-choice property is what makes the algorithm work in one pass. You never need to go back and reconsider earlier decisions.

Edge cases to watch for

Before submitting, make sure your solution handles these:

• All negative like [-3, -5, -1, -8]: answer is -1 (the least negative element). Do not return 0.
• Single element [5]: answer is 5. [-3]: answer is -3.
• All positive like [1, 2, 3]: the entire array is the max subarray. Sum = 6.
• Negative then positive like [-1, 5]: restart at 5 gives sum = 5, not 4.
• One large negative in the middle like [5, -100, 5]: the negative splits the subarray. Answer is 5, not -90.

Kadane's algorithm handles all of these correctly with no special cases.

The building blocks

This problem is built on two reusable patterns:

1. Linear DP with constant state. The recurrence dp[i] = max(nums[i], dp[i-1] + nums[i]) only looks back one step. That means you can replace the DP array with a single variable, giving O(1) space. This is the exact same optimization pattern from Climbing Stairs and House Robber. Different recurrence, same brick.

2. Running max. You maintain max_sum as you iterate, updating it whenever current_sum beats the current record. This is the mirror image of the running min pattern from Best Time to Buy and Sell Stock. In that problem, you track the minimum price seen so far. Here, you track the maximum subarray sum seen so far. Same idea, different direction.

These two building blocks combine to give you Kadane's algorithm. Once you recognize them individually, the solution writes itself: "linear DP with one-step lookback, plus a running max to capture the overall answer."

From understanding to recall

You have just read through Kadane's algorithm and the extend-or-restart decision makes complete sense. But understanding and reproducing are different skills. In an interview, you will not have this walkthrough in front of you. You need to write the solution from scratch, and the pressure of a ticking clock makes it easy to freeze on details you thought you knew.

Spaced repetition is designed for this. Instead of solving Maximum Subarray once and forgetting the details in two weeks, you revisit the extend-or-restart pattern at increasing intervals. Each time you write the code from memory. After a few reps, the decision logic and initialization are automatic.

The extend-or-restart DP pattern and the running max are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than solving problems one at a time and hoping the patterns stick.

Related posts

• Best Time to Buy and Sell Stock - The running min pattern, Kadane's close cousin for single-pass optimization
• Climbing Stairs - The simplest linear DP with constant state, the same skeleton Kadane's uses