Module 22 · Greedy Algorithms and Kadane-Style State

212. Maximum Subarray Sum

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the largest sum of a nonempty contiguous subarray of an integer list. Negative values are allowed. Return None for empty input. Do not mutate nums; selecting the empty subarray is not permitted for nonempty input.

Examples

Example 1

max_subarray([-2,1,-3,4,-1,2,1,-5,4])
=> 6

The interval [4,-1,2,1] gives the largest sum.

Example 2

max_subarray([-5,-2,-9])
=> -2

A nonempty all-negative answer is the least negative singleton.

Example 3

max_subarray([])
=> None

No nonempty subarray exists.

Reveal the worked solution and reasoning

Why this mechanism works

Consider the best subarray ending exactly at the current position. It either starts here or extends the best ending at the previous position. A negative previous sum is harmful and should be discarded. Keep this local ending state separate from the best answer anywhere.

State and boundaries

ending is the largest sum of a nonempty subarray ending at the last processed index. best is the largest such sum over all processed endpoints.

Protocol

Handle empty input.
Initialize both states to the first value.
Set ending=max(current,ending+current).
Update best from ending.
Return best.

Visualization

[-2,1,-3,4,-1,2,1,-5,4]
at 4: restart rather than extend -2
extend 4,-1,2,1 -> sum 6

Python implementation

def max_subarray(nums):
    if not nums:
        return None
    ending = best = nums[0]
    for i in range(1, len(nums)):
        ending = max(nums[i], ending + nums[i])
        best = max(best, ending)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

max_subarray([-2,1,-3,4,-1,2,1,-5,4])

L2 max_subarray: if not nums:
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]

L4 max_subarray: ending = best = nums[0]
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=-2; best=-2

L5 max_subarray: for i in range(1, len(nums)):
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=-2; best=-2; i=1

L6 max_subarray: ending = max(nums[i], ending + nums[i])
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=1; best=-2; i=1

L7 max_subarray: best = max(best, ending)
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=1; best=1; i=1

L5 max_subarray: for i in range(1, len(nums)):
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=1; best=1; i=2

L6 max_subarray: ending = max(nums[i], ending + nums[i])
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=-2; best=1; i=2

L5 max_subarray: for i in range(1, len(nums)):
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=-2; best=1; i=3

... 10 intermediate state changes omitted ...

L5 max_subarray: for i in range(1, len(nums)):
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=6; best=6; i=7

L6 max_subarray: ending = max(nums[i], ending + nums[i])
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=1; best=6; i=7

L5 max_subarray: for i in range(1, len(nums)):
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=1; best=6; i=8

L6 max_subarray: ending = max(nums[i], ending + nums[i])
nums=[-2, 1, -3, 4, -1, 2, 1, -5, ...]; ending=5; best=6; i=8

Result: 6. The interval [4,-1,2,1] gives the largest sum.

max_subarray([-5,-2,-9])

L2 max_subarray: if not nums:
nums=[-5, -2, -9]

L4 max_subarray: ending = best = nums[0]
nums=[-5, -2, -9]; ending=-5; best=-5

L5 max_subarray: for i in range(1, len(nums)):
nums=[-5, -2, -9]; ending=-5; best=-5; i=1

L6 max_subarray: ending = max(nums[i], ending + nums[i])
nums=[-5, -2, -9]; ending=-2; best=-5; i=1

L7 max_subarray: best = max(best, ending)
nums=[-5, -2, -9]; ending=-2; best=-2; i=1

L5 max_subarray: for i in range(1, len(nums)):
nums=[-5, -2, -9]; ending=-2; best=-2; i=2

L6 max_subarray: ending = max(nums[i], ending + nums[i])
nums=[-5, -2, -9]; ending=-9; best=-2; i=2

Result: -2. A nonempty all-negative answer is the least negative singleton.

Why the solution is correct

Every subarray ending at the current index is either the singleton or a previous ending subarray plus the current value. Extending the maximum previous ending sum is optimal among extensions. Taking the maximum with the singleton gives the exact state, and the global maximum covers every endpoint.

Time and space

O(n) time and O(1) auxiliary state.

Common mistakes

Initializing best to zero incorrectly returns an empty-subarray result on all-negative input. Updating best from the raw current value misses multi-element runs.

Reasoning card

State: ending is the largest sum of a nonempty subarray ending at the last processed index. best is the largest such sum over all processed endpoints.

Invariant: ending_here is the best nonempty subarray ending exactly here.

Decision to rehearse: At each value, extend the previous best-ending-here or restart.

Finish: Return best

Transfer exercise

Track the candidate start index whenever the recurrence restarts, then return an optimal half-open interval.