Maximum Subarray
mediumTime: O(n)Space: O(1)
The shape of the problem
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.