Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product within the array and return it.

A subarray is a contiguous non-empty sequence of elements within an array. You can assume the output will fit into a 32-bit integer.

• 1 ≤ nums.length ≤ 1000
• -10 ≤ nums[i] ≤ 10

Examples

How to think about it

A subarray product can change drastically because of two main factors:

• Negative numbers: They can flip a massive maximum product into a massive minimum product, and vice versa.
• Zeros: They reset the product completely. Any subarray containing a zero will have a product of 0.

Because multiplying by a negative number flips the sign, we cannot just keep track of the maximum product so far. A highly negative running product (the minimum) could instantly become the new maximum if we multiply it by another negative number.

Approaches

1. Brute Force — O(n²) Time, O(1) Space

Fix a starting index, then keep multiplying elements to the right while tracking the maximum product seen. This evaluates every possible contiguous subarray explicitly but is too slow for large inputs.

2. Kadane's Algorithm (Dynamic Programming) — O(n) Time, O(1) Space ✓

In the classic maximum-sum subarray, we only track the current max sum. For products, we must track two values at every step:

• curMax: The maximum product ending at the current index.
• curMin: The minimum product ending at the current index.

When processing num, the new curMax could be num itself, num * curMax, or num * curMin (if both are negative). We update both curMax and curMin iteratively.

3. Prefix & Suffix Products — O(n) Time, O(1) Space ✓

A maximum product subarray will always be either a prefix product of a zero-free segment or a suffix product of that segment. If there's an even number of negatives, the whole segment is positive. If odd, dropping the prefix up to the first negative or the suffix up to the last negative yields the maximum. Scanning left-to-right (prefix) and right-to-left (suffix) efficiently computes this without explicitly counting negatives.

Common Pitfalls

Ignoring Negative Numbers

Unlike max sum subarray, a very negative product can become the max after multiplying by another negative. Tracking only the current max is insufficient.

Forgetting to Handle Zeros

A zero resets the product to zero and effectively splits the array. In Prefix/Suffix approach, we must reset the running product to 1 if it becomes 0 (e.g., prefix = prefix or 1).

Not Saving the Previous Maximum (Kadane's)

When computing the new curMin, it may depend on the old curMax. If you update curMax first and then use it directly to compute curMin, you'll get wrong results. Always store curMax * num in a temporary variable first.