Maximum Subarray
Picture
For [4,−7,5], carrying 4−7 into the last value gives 2. Restarting at 5 is better.
Predict
For an all-negative list, may the answer be zero?
Walk through the small example
No, if the subarray must be nonempty. The only history needed is the best sum ending immediately before this position.
Mental model and complete Python solution
Every valid subarray ending here either starts here or extends one ending just before. Those are exhaustive and collapse all earlier histories into one best extension.
What the function promises: Return the maximum sum of a nonempty sequence. Raise ValueError for empty input.
def maximum_subarray(values):
if not values:
raise ValueError("Nonempty input required")
ending = best = values[0]
for value in values[1:]:
ending = max(value, ending + value)
best = max(best, ending)
return best
assert maximum_subarray([-2,1,-3,4,-1,2,1,-5,4]) == 6
assert maximum_subarray([-5,-2]) == -2Work and storage: O(n) time and O(1) extra space.
When to recognize it: The only history needed is the best sum ending immediately before this position.
Check before applying it: Resetting negative totals to zero accidentally permits an empty answer when all values are negative.
Change one rule
Return the chosen subarray too.
See what changes
Track the start when restarting and snapshot both endpoints whenever the global best improves.
Connect
one dimensional: A one-coordinate DP can often compress to one previous value.
windows: Unlike a window, negative values do not give monotone pointer moves.