DSA Maximum Subarray (Kadane's)

The problem

The maximum subarray problem asks for the largest sum of a subarray. A subarray is one unbroken run of neighbouring values in a list.

The input is a list of numbers. The output is one sum. The run must hold at least one value, and its values must sit side by side in the list.

cases = [
    ([-2, 1, -3, 4, -1, 2, 1, -5, 4], 6),
    ([-5, -2, -8], -2),
    ([1], 1),
    ([5, 4, -1, 7, 8], 23),
    ([2, -1, 2], 3),
]
for nums, expected in cases:
    print("nums", nums, "best sum:", expected)

The first list answers 6, from the run [4, -1, 2, 1]. The all-negative list answers -2. Its best run is the single value -2.

Intuition: the total sum and the positives both mislead

One first idea is the sum of the whole list. That sum mixes strong stretches with weak ones. The weak ends drag it down.

A second idea is adding only the positive values. Those values need not sit side by side. Their sum describes no subarray at all.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("whole list sum:", sum(nums))
print("positives only sum:", sum(x for x in nums if x > 0))
print("best subarray sum:", 6)

The whole list sums to 1. The positives sum to 12, but they are scattered across the list. The answer, 6, belongs to one unbroken run.

So the search must respect position. A run is defined by where it starts and where it ends.

Brute force: check every start and end

The brute force picks every start index and every end index at or after it. It sums each run and keeps the largest sum. No run is missed.

def brute(nums):
    best = nums[0]
    checked = 0
    for start in range(len(nums)):
        total = 0
        for end in range(start, len(nums)):
            total += nums[end]
            checked += 1
            if total > best:
                best = total
    return best, checked

for nums in [[-2, 1, -3, 4, -1, 2, 1, -5, 4], [-5, -2, -8]]:
    best, checked = brute(nums)
    print("nums", nums, "best:", best, "subarrays checked:", checked)

Nine values give 45 subarrays. The count grows with the square of the length. A list ten times as long has about a hundred times as many runs.

The optimal solution: the best sum ending here

The state is the ending-here sum, the best sum of a subarray that ends at the current position. That one sentence carries the whole method, which is called Kadane's algorithm.

At each value there are two options. Extend the run that ends just before it. Or restart a new run at this value. The larger sum becomes the new ending-here sum, and the best sum seen is updated.

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

cases = [[-2, 1, -3, 4, -1, 2, 1, -5, 4], [-5, -2, -8], [1], [5, 4, -1, 7, 8], [2, -1, 2]]
for nums in cases:
    print("nums", nums, "best sum:", max_subarray(nums))

All five cases from section 1 pass. One pass over the list is enough. A negative ending-here sum is dropped by restarting, never carried forward.

Walkthrough: scanning the first list

Follow the scan over [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Each printed line shows the ending-here sum and the best sum after one value. Watch the restarts at 1 and at 4.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
ending = nums[0]
best = nums[0]
print("value", nums[0], "ending here:", ending, "best:", best)
for x in nums[1:]:
    ending = max(x, ending + x)
    best = max(best, ending)
    print("value", x, "ending here:", ending, "best:", best)

The value 1 restarts the run, because -2 + 1 is worse than 1 alone. The value 4 restarts again for the same reason. From 4 the run grows through -1, 2 and 1.

At the value 1 in position six the ending-here sum reaches 6. That value is the best sum. The final 4 lifts the ending-here sum only to 5, so the best stays 6.

Complexity

Kadane's algorithm makes one pass and does a fixed amount of work per value, so the time is O(n).

It carries only two sums, the ending-here sum and the best sum, so the extra space is O(1).

def brute_checked(n):
    return n * (n + 1) // 2

for n in [10, 20, 40]:
    print("values", n, "brute force subarrays:", brute_checked(n), "kadane steps:", n)

Doubling the list roughly quadruples the brute force count. The single pass merely doubles. The printed counts show both growth rates.

Edge cases and pitfalls

An all-negative list is the case that breaks careless code. The answer is its largest single value. A run must hold at least one value, so answering 0 is wrong.

Code that starts both sums at 0 makes exactly that mistake. The sums must start at the first value. That start handles negative lists with no special case.

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

print("all negative:", max_subarray([-5, -2, -8]))
print("one value:", max_subarray([-7]))
print("all positive:", max_subarray([1, 2, 3]))
print("one dip:", max_subarray([4, -1, 4]))

An empty list has no subarray at all. This problem gives it no answer. The code above reads the first value, so an empty list must be ruled out by the caller, not passed in.