Maximum Product Subarray — Step-by-Step Visualization

Algorithm Pattern

Dynamic Programming (Dual-State)

Key Idea

Because of negative numbers, the minimum product can suddenly become the maximum product when multiplied by another negative number. Thus, we must track both the maximum AND the minimum product ending at the current position. For each number, the new `max` and `min` could be chosen from: the number itself, `num * currentMax`, or `num * currentMin`.

Step-by-Step Approach

1. Initialize `res = max(nums)`, `curMin = 1`, `curMax = 1`.
2. Iterate through each number `n` in `nums`.
3. Calculate `tmp = curMax * n`.
4. Update `curMax = max(n * curMax, n * curMin, n)`.
5. Update `curMin = min(tmp, n * curMin, n)`.
6. Update `res = max(res, curMax)`.
7. Return `res`.

Common Gotchas

• Handle zeros in the array (they reset the current products).
• Always use a temporary variable for `curMax` before updating `curMin` in the same iteration.