Maximum Product Subarray

How it works

The key idea is that the maximum product subarray must appear as either:

• a prefix product of some segment, or
• a suffix product of some segment.

Why this works:

• Negative numbers flip signs. If a subarray has an even number of negatives, the full product is positive.
• If it has an odd number of negatives, removing either:
  • the prefix up to the first negative, or
  • the suffix after the last negative
    will give the maximum product.
• Zeros break subarrays completely, so products must restart after a zero.

By scanning:

• once from left to right (prefix)
• once from right to left (suffix)

we implicitly consider all valid subarrays without explicitly tracking negatives.

The (prefix or 1) trick resets the product after encountering 0.

Steps

1. Initialize:
   • res as the first element.
   • prefix = 0, suffix = 0.
2. For i from 0 to n - 1:
   • Update prefix product:
     • prefix = nums[i] * (prefix if prefix != 0 else 1).
   • Update suffix product:
     • suffix = nums[n - 1 - i] * (suffix if suffix != 0 else 1).
   • Update result:
     • res = max(res, prefix, suffix).
3. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Ignoring Negative Numbers Can Become Positive

Unlike maximum sum subarray, a very negative product can become the maximum after multiplying by another negative number. Tracking only the current maximum is insufficient. You must track both curMax and curMin because multiplying curMin by a negative number might produce the new maximum.

Forgetting to Handle Zeros

A zero in the array resets the product to zero and effectively splits the array. After encountering a zero, the subarray must restart fresh. Failing to handle this case causes the algorithm to carry forward zero products incorrectly.

Not Saving the Previous Maximum Before Updating

When computing the new curMax and curMin, the calculation for curMin may depend on the old value of curMax. Updating curMax first and then using the new value to compute curMin produces wrong results. Always store curMax * num in a temporary variable before updating either value.

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n, res = len(nums), nums[0]
        prefix = suffix = 0

        for i in range(n):
            prefix = nums[i] * (prefix or 1)
            suffix = nums[n - 1 - i] * (suffix or 1)
            res = max(res, max(prefix, suffix))
        return res

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size(), res = nums[0];
        int prefix = 0, suffix = 0;

        for (int i = 0; i < n; i++) {
            prefix = nums[i] * (prefix == 0 ? 1 : prefix);
            suffix = nums[n - 1 - i] * (suffix == 0 ? 1 : suffix);
            res = max(res, max(prefix, suffix));
        }
        return res;
    }
};