Maximum Subarray

Interview Prep

Warm-upDynamic Programmingarraysdpkadane

The problem

Given an array of integers (positive, negative, or zero), find the contiguous non-empty subarray with the largest sum. Return the sum.

Pattern: at each position, extend or restart

The key insight: at every position i, the best subarray ending at i is either the single element nums[i] alone, or nums[i] plus the best subarray ending at i-1. Take the max, update the global best. This is Kadane's algorithm, and it's the most elegant DP in the interview canon.

The recurrence is one line: current = max(nums[i], current + nums[i]). If current went negative, restarting from i is strictly better than dragging that liability forward.

Brute force: every subarray

Two nested loops: for each start, sum forward. O(n²) time, O(1) space. Correct, slow. 

def max_subarray_brute(nums: list[int]) -> int:
    best = nums[0]
    for i in range(len(nums)):
        s = 0
        for j in range(i, len(nums)):
            s += nums[j]
            best = max(best, s)
    return best

Optimal: Kadane's in O(n)

def max_subarray(nums: list[int]) -> int:
    """Kadane's algorithm."""
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)     # extend or restart
        best = max(best, current)
    return best

Trace

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

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   (the subarray [4, -1, 2, 1])

Complexity

Variations worth knowing