Maximum Subarray

You'll solve it with dynamic programming (DP) by tracking one number: the best sum that ends at the current position. This is often called Kadane's algorithm. You need running sums and maximums. Related chapter: dynamic programming.

1. The problem

You get a nonempty list of integers. Return the largest sum of any subarray. A subarray is a run of neighboring numbers, and it must hold at least one. Numbers can be negative, and you can't skip any inside a subarray. Don't change the input. This is LeetCode 53.

The all-negative case is the trap. You must pick at least one number, so the answer can be negative.

2. A correct baseline

def baseline(nums):
    best=nums[0]
    for start in range(len(nums)):
        total=0
        for end in range(start,len(nums)):
            total+=nums[end]
            best=max(best,total)
    return best

assert baseline([4,-6,3,2,-1,4])==8
assert baseline([-5,-2,-7])==-2
assert baseline([0])==0

This takes O(n²) time: the work grows with the square of the list's length. On 100,000 numbers, that's about five billion additions. It uses O(1) extra space.

The bottleneck. It tracks every start separately. But to extend to the next position, only the best sum ending at the current one matters.

3. The observation

In [4,-6,3,2,-1,4], the best subarray ending at the -6 is [4,-6], with sum -2. Now the 3 arrives. Should it extend [4,-6]? That gives 1. Starting fresh gives 3, which is better. A negative sum so far only drags the next number down.

So the best subarray ending at position i has two options. It's nums[i] alone, or it extends the best subarray ending at i − 1. Take the larger. Keep the best of these over every position as the answer. This works because every subarray ends somewhere, so checking the best one ending at each position covers them all.

4. The solution and a trace

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        """Requires a nonempty integer list; select at least one element."""
        ending=best=nums[0]
        for i in range(1,len(nums)):
            value=nums[i]
            ending=max(value,ending+value)  # Best sum ending exactly at i.
            best=max(best,ending)
        return best

solve=Solution().maxSubArray
assert solve([4,-6,3,2,-1,4])==8
assert solve([-5,-2,-7])==-2
assert solve([0])==0

Trace [4,-6,3,2,-1,4]:

5. Why it works

What stays true. After step i, ending is the best sum of a subarray that ends exactly at i.

Why it stays true. A subarray ending at i is either nums[i] alone, or a subarray ending at i − 1 plus nums[i]. The best of the second kind uses the best ending at i − 1, which is ending. So max(value, ending + value) picks the best of all of them.

Why best is the answer. Every subarray ends at some position. best is the largest ending over all positions, so it covers every subarray.

6. Cost, edge cases, and failure

Cost. One pass: O(n) time, growing in step with the list. O(1) extra space.

Edge cases. Start from the first number, not from zero, because an empty subarray isn't allowed. A negative number in the middle can still belong to the best subarray, as in [4,-1,4].

Where it fails. Starting from zero, or skipping negative numbers, gives wrong answers:

assert solve([-5,-2,-7])==-2  # A zero-initialized global best would incorrectly return 0.
assert solve([4,-1,4])==7
assert sum(v for v in [4,-1,4] if v>0)==8  # Filtering negatives breaks consecutiveness.

import random
rng=random.Random(53)
for _ in range(1000):
    nums=[rng.randint(-10,10) for _ in range(rng.randint(1,25))]
    before=nums.copy()
    assert solve(nums)==baseline(nums)
    assert nums==before