LeetCode Maximum Subarray: Kadane's Algorithm Explained

Maximum Subarray is LeetCode problem 53, rated Medium. It is the canonical introduction to Kadane’s algorithm, and once you understand why it works you understand the core idea behind one-dimensional dynamic programming.

The Problem

Given an integer array nums, find the contiguous subarray with the largest sum and return that sum. The subarray must have at least one element.

Example:

Input:  nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The subarray [4, -1, 2, 1] has sum 6.

“Contiguous” is the operative word. We are not picking arbitrary elements; we are picking a window.

Brute Force

Try every subarray, sum it, track the max.

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

Time: O(n^2). Space: O(1). The naive triple-loop version is O(n^3); we avoided that by accumulating current as we extend j. For n = 10^5, even O(n^2) is too slow.

Optimal Solution

Kadane’s algorithm asks at each index: “what is the maximum sum of a subarray ending exactly here?” That value, call it current, has a simple recurrence: either extend the previous best ending subarray, or start fresh at this element.

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

Line by line:

• current holds the maximum subarray sum that ends at the index we are processing.
• best is the global answer so far.
• For each new element, decide: should I start a brand new subarray here, or extend the previous one? Whichever yields a larger sum wins.
• Update best whenever current improves.

The reason this works is monotone in a subtle way. If current + x < x, then current was negative, and dragging it forward can only hurt. Throw it away.

Walk Through an Example

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4].

• Start: current = -2, best = -2.
• x = 1. current = max(1, -2 + 1) = 1. best = 1.
• x = -3. current = max(-3, 1 + -3) = -2. best = 1.
• x = 4. current = max(4, -2 + 4) = 4. best = 4.
• x = -1. current = max(-1, 4 + -1) = 3. best = 4.
• x = 2. current = max(2, 3 + 2) = 5. best = 5.
• x = 1. current = max(1, 5 + 1) = 6. best = 6.
• x = -5. current = max(-5, 6 + -5) = 1. best = 6.
• x = 4. current = max(4, 1 + 4) = 5. best = 6.

Return 6.

Edge Cases

• All negative numbers like [-3, -1, -2]. The answer is the single largest element, here -1. The algorithm handles this because we initialize with nums[0] and use max(x, current + x) rather than clamping to 0.
• Single element. Return that element.
• All zeros. Return 0.
• Mixed signs with a strong positive run at the end. Make sure your best actually updates inside the loop.
• Asked for the subarray itself, not just the sum. Track start and end indices alongside current and best.

Complexity Analysis

• Time: O(n). One pass.
• Space: O(1). Two scalars.

A divide and conquer solution exists at O(n log n) and is a fun whiteboard exercise, but it is strictly slower than Kadane’s and not what interviewers want.

How to Explain It in an Interview

• Restate the problem and confirm “contiguous” and “at least one element.”
• Mention brute force at O(n^2) so they know you see the baseline.
• State the Kadane insight: “I will compute, for each index, the best subarray ending there. The recurrence is take this element alone or extend the previous best.”
• Justify dropping a negative running sum: it can only hurt.
• Code it, then walk through a small example.
• Mention the all-negative edge case explicitly. That is what separates juniors from people who have actually tested their code.

Related Problems

• LeetCode 152 Maximum Product Subarray
• LeetCode 918 Maximum Sum Circular Subarray
• LeetCode 121 Best Time to Buy and Sell Stock
• LeetCode 198 House Robber
• LeetCode 1480 Running Sum of 1d Array

If you want to see how the same “extend or restart” idea generalizes, the sliding window technique post is the natural next read.

Wrap up

Kadane’s algorithm is small enough to fit on a sticky note and deep enough to be a poster child for dynamic programming. The mental model, “what is the best answer ending right here, given the best answer ending one step back”, scales up to longest increasing subsequence, edit distance, and most of the DP canon. Learn it here so you can lean on it later.