Find the maximum sum contiguous subarray in linear time. At each position decide: extend the current subarray or start fresh? Tracks the best seen so far as a DP recurrence.
time:O(n)
space:O(1)
⚡ +200_XP
step[1/23]
> Start
cur
-2
1
-3
4
-1
2
1
-5
4
▸Find the contiguous subarray with the largest sum in [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// tap NEXT STEP to walk through one step at a time