Maximum Product Subarray
Medium1-D dynamic programming
Given an array of integers nums, find the non-empty run of neighbouring values whose product is largest, and return that product.
Examples
Input: nums = [3, -1, 4, 2] Output: 8
4 × 2. Any run that includes -1 is negative.
Input: nums = [-2, 3, -4] Output: 24
The whole array: its two negatives cancel out.
Constraints
1 ≤ nums.length ≤ 2 × 10⁴-10 ≤ nums[i] ≤ 10- The product of any run fits in a 32-bit integer.
Stuck?
Hint 1
A negative number turns the smallest product so far into the largest. So the best product ending here comes from the best or the worst product ending one step earlier.
Hint 2
Keep both the largest and the smallest product of a run ending at the current value; a zero restarts both. Track the best largest you have seen.
The idea
Multiplying by a negative value turns the smallest product into the largest, and the largest into the smallest. So for the runs ending at each value, keep both the largest and the smallest product. The next largest comes from one of the two, or from starting fresh at the new value.
Time O(n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
high and low are the largest and smallest products of a run ending at the current value. At the first value the only run is that value. best starts there too, not at 0, since an array holding one negative value must return it.
function maxProduct(nums) { let high = nums[0]; let low = nums[0]; let best = nums[0]; for (let i = 1; i < nums.length; i++) { const value = nums[i]; const nextHigh = Math.max(value, high * value, low * value); const nextLow = Math.min(value, high * value, low * value); high = nextHigh; low = nextLow; best = Math.max(best, high); } return best;}The trap
Keeping only the largest product ending at each value is the trick that solves the maximum sum problem, so it looks like it carries over. Products do not behave like sums: once a run's product goes negative it is dropped, but a second negative value later would have turned it into the largest product. Arrays where two negatives cancel across other values come out too small.
function maxProduct(nums) { let current = nums[0]; let best = nums[0]; for (let i = 1; i < nums.length; i++) { current = Math.max(nums[i], current * nums[i]); // forgets the smallest product best = Math.max(best, current); } return best;}