Pattern visualizer
Maximum Product Subarray
Kadane's sum logic fails here because multiplication is sign-sensitive: a huge negative running product can become a huge positive one the moment another negative arrives — but only if we REMEMBER it. So each index keeps two runners: curMax and curMin, the best AND worst products of subarrays ending right there. A negative element swaps their roles before they absorb it. Animated on: Find the contiguous subarray of [2,3,-2,4,-1,3] with the largest PRODUCT..
Track max AND min ending here
time O(n)space O(1)step 1 / 9
2
[0]3
[1]-2
[2]4
[3]-1
[4]3
[5]line 2
Seed both runners with the first cell: curMax = curMin = best = 2. curMax is the best product ending here, curMin the WORST — keep it, negatives can resurrect it.
Pseudocode
1FUNCTION maxProduct(nums):2 set curMax, curMin and best all to nums[0]3 FOR each x in nums from index 1 onward:4 IF x < 0: swap curMax and curMin5 curMax = the larger of x and (curMax * x)6 curMin = the smaller of x and (curMin * x)7 best = the larger of best and curMax8 RETURN best
← / → step · space play · Home restart