Maximum Subarray
LeetCode 53 • Medium • Arrays
Find the contiguous subarray with the largest sum. Return the sum. Kadane: track current_sum and max_sum; reset current_sum when it goes negative.
TimeO(n)single pass
SpaceO(1)two variables
current_sum: —
max_sum: —
Ready
Press Play. Kadane's algorithm: for each element, either extend current_sum or reset to the element. Update max_sum when current exceeds it.
TimeO(n log n)divide & conquer
SpaceO(log n)call stack
Recursive: maxSub(l, r) — base when l≥r return (sum, max, prefix, suffix). Split mid; max = max(left, right, cross). Cross = left_suffix + right_prefix.
3
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.
PATTERN ▸ Extend or restart at each element O(n) · O(1)
① INIT
current_sum = nums[0]
max_sum = nums[0]
② LOOP
for i in range(1, len(nums)):
③ EXTEND OR RESTART
current_sum = max(nums[i], current_sum + nums[i])
④ TRACK BEST
max_sum = max(max_sum, current_sum)
⑤ RETURN
return max_sum
PATTERN ▸ solve returns (total, best, prefix, suffix) O(n log n) · O(log n)
① BASE CASE
if l >= r: return (nums[l], nums[l], nums[l], nums[l])
② SPLIT
mid = (l+r)//2
L = solve(l,mid); R = solve(mid+1,r)
③ COMBINE
cross = L[3] + R[2]
best = max(L[1], R[1], cross)
④ RETURN
return (total, best, prefix, suffix)
▼ your implementation ▼
Verify your solution: