Problem Statement

Maximum Subarray

You are given a list of numbers called nums. Some are positive, some are negative. A subarray is a chunk of numbers that sit next to each other in the list, with no gaps. Your job is to pick the chunk whose numbers add up to the biggest total, and return that total. The chunk has to be in one piece (contiguous) and cannot be empty.

mediumArrayDynamic ProgrammingDynamic ProgrammingTime: O(n) · Space: O(1)

Translate the prompt

Find the contiguous subarray (non-empty) with the largest sum. Works on mixed positive and negative values.

Signals to notice

contiguous subarraynegative numbers allowedrunning sum with reset

Brute force first

Try every (i, j) pair and sum between them: O(n³) trivially or O(n²) with a running sum. Still too slow on large inputs.

The key insight

At each position i, the best subarray ENDING at i is either just `nums[i]` alone or `nums[i]` appended to the best subarray ending at i-1. Those are the only two candidates.

Trace it on `nums=[-2,1,-3,4,-1,2,1,-5,4]`

v=-2  cur=-2       best=-2
v= 1  cur=max(1,-1)=1   best=1
v=-3  cur=max(-3,-2)=-2 best=1
v= 4  cur=max(4,2)=4    best=4
v=-1  cur=max(-1,3)=3   best=4
v= 2  cur=max(2,5)=5    best=5
v= 1  cur=max(1,6)=6    best=6
v=-5  cur=max(-5,1)=1   best=6
v= 4  cur=max(4,5)=5    best=6 → return 6

What must stay true

After step i, `cur` = max sum of any subarray ending exactly at i, and `best` = max of `cur` over all positions processed.

Shape of the loop

cur = best = nums[0]
for v in nums[1:]:
  cur = max(v, cur + v)
  best = max(best, cur)
return best

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Initializing `best` to 0. If every element is negative, the correct answer is the largest (least-negative) single element, not 0.

Dynamic Programming Pattern