-2
1
-3
4
-1
2
1
-5
4
[0][1][2][3][4][5][6][7][8]
Brute force
▸1best ← −∞2for i ← 0 to n − 1:3 for j ← i to n − 1:4 best ← max(best, sum(nums[i..j]))56return best
state
- n9
- best−∞
warming up the animation
Given an integer array, find the contiguous subarray with the largest sum and return that sum.
▸1best ← −∞2for i ← 0 to n − 1:3 for j ← i to n − 1:4 best ← max(best, sum(nums[i..j]))56return best
line 1Goal: the largest sum among all CONTIGUOUS subarrays. The brute approach is literal, fix a start i, extend an end j, sum that window, and keep the maximum seen.