LeetCode 152 Maximum Product Subarray - Tracking Two States

The fix is to track two values at each position:

$1.$ $maxProd[i]$: the maximum product of any subarray ending at index $i$

$2.$ $minProd[i]$: the minimum product (most negative) of any subarray ending at index $i$

Why track the minimum? Because when you hit a negative number, the minimum becomes the maximum and vice versa. The most negative product, multiplied by a negative, becomes the most positive.

The recurrence for each position $i$: $maxProd[i] = \max(nums[i], maxProd[i-1] \times nums[i], minProd[i-1] \times nums[i])$ $minProd[i] = \min(nums[i], minProd[i-1] \times nums[i], maxProd[i-1] \times nums[i])$

Each position has three choices: start fresh with $nums[i]$, extend the previous maximum, or extend the previous minimum. You take the best for max and the worst for min.