Find the contiguous subarray with the largest product. Return that product.
DSA Animator › DSA Revision › Dynamic Programming › Maximum Product Subarray
Remember: with products, keep both the maximum and the minimum. A negative number swaps their roles. The video solves Maximum Product Subarray (LeetCode 152, Medium) with the Track Max and Min pattern from the Dynamic Programming topic, and you can replay every step in the interactive Maximum Product Subarray animation.
Find the contiguous subarray with the largest product. Return that product.
For 2, minus 5, minus 2, minus 4, 3, the answer is 24. It comes from minus 2, minus 4, 3.
Multiplying every subarray is O of n squared. Kadane style tracking of only the maximum fails, because a negative number turns the smallest product into the largest.
Track two values for subarrays ending at the current index: the largest product and the smallest product. The smallest one matters because it may be a big negative number. When the current number is negative, swap the two before updating. Then the new maximum is the larger of the number itself and the maximum times the number, and the minimum likewise. Keep the best maximum seen anywhere.
Start at 2, with maximum 2, minimum 2, and best 2. Minus 5 swaps them, so the maximum becomes minus 5 and the minimum becomes minus 10. Minus 2 swaps again, and the old minimum times minus 2 makes the maximum 20. Minus 4 makes the maximum 8 and the minimum minus 80. Then 3 makes the maximum 24, the product of minus 2, minus 4 and 3. The best is 24.
In code, set max, min and best to the first number. For each next number, swap max and min if it is negative. Update max as the larger of x and max times x, and min as the smaller of x and min times x. Update best with max, so it's O of n time and O of 1 space.
Remember: with products, keep both the maximum and the minimum. A negative number swaps their roles.