Pattern visualizer
Kadane's Algorithm
The key insight: once your running total goes negative, it can only drag down whatever you add next — so there's never a reason to keep it. At each number, compare 'keep extending my current run' vs. 'give up on it and restart fresh right here', and always take whichever is bigger. One pointer (curr) tracks that running total; a second (best) just remembers the highest curr has ever been. Because a bad run gets abandoned the instant it turns negative, one left-to-right pass is enough — no need to check every possible subarray. Animated on: Find the contiguous subarray with the largest sum..
Maximum subarray sum in one linear pass
Seed both curr and best with the first element: curr = best = -2. curr always means 'best subarray sum ending right here'.
1FUNCTION maxSubArray(nums):2 set curr and best both to nums[0]3 FOR i from 1 to (length of nums) - 1:4 curr = the larger of nums[i] and (curr + nums[i])5 best = the larger of best and curr6 RETURN best
← / → step · space play · Home restart