Maximum Product Subarray: The Hidden Trap of Negative Numbers

The Maximum Product Subarray problem (LeetCode 152) looks deceptively similar to the Maximum Sum Subarray problem (Kadane's Algorithm). However, there is a catch: negative numbers.

In this post, we will explore why a standard greedy approach fails and how tracking both the maximum and minimum values solves the problem elegantly in linear time.

The Problem Statement

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The Intuition: Why Negative Numbers Matter

If the array only contained positive numbers, we could simply keep multiplying. The more numbers we include, the larger the product becomes.

However, negative numbers flip the sign:

• A negative number multiplied by a large positive number becomes a large negative number (very bad).
• A negative number multiplied by a large negative number becomes a large positive number (very good).

This means that at any point, the minimum product (the most negative number) is just as important as the maximum product, because the next negative number could instantly turn that minimum into a new maximum.

The Algorithm

Instead of just maintaining one variable current_max, we maintain two variables as we iterate through the array:

1. max_cur: The maximum product ending at the current position.
2. min_cur: The minimum product ending at the current position.

At every step, for a number nums[i], we have three choices for the new maximum:

• The number itself (starting a new subarray).
• The number multiplied by the previous maximum.
• The number multiplied by the previous minimum (if nums[i] is negative).

The Code

Here is the optimized C++ solution that runs in O(N) time and O(1) space. Time: O(N) Space: O(1)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max_cur, min_cur, ans;

        // Initialize with base values
        max_cur = 1;
        min_cur = 1;
        ans = nums[0];

        for(int i = 0; i < nums.size(); i++) {
            // If we encounter a zero, the product chain breaks,
            // but the logic below naturally handles starting fresh
            // because we compare against nums[i] itself.

            // Store max_cur * nums[i] in temp because max_cur gets updated
            int temp = max_cur * nums[i];

            // We take the max of 3 things:
            // 1. Current number alone (restart)
            // 2. Current * Prev Max (continue positive chain)
            // 3. Current * Prev Min (negative * negative = positive)
            max_cur = max(temp, max(min_cur * nums[i], nums[i]));

            // We calculate new min similarly
            min_cur = min(temp, min(min_cur * nums[i], nums[i]));

            // Update global answer
            ans = max(ans, max_cur);
        }
        return ans;
    }
};

Dry Run

Let's trace [2, 3, -2, 4]:

• i=0 (Val 2): max_cur=2, min_cur=2, ans=2
• i=1 (Val 3): max_cur=6, min_cur=3, ans=6
• i=2 (Val -2):
  temp = 6 * -2 = -12
  max_cur = max(-12, 3 * -2, -2) = -2
  min_cur = min(-12, -6, -2) = -12
  ans = 6
• i=3 (Val 4):
  temp = -2 * 4 = -8
  max_cur = max(-8, -12 * 4, 4) = 4 (Started fresh!)
  min_cur = min(-8, -48, 4) = -48
  ans = 6

Conclusion

The key takeaway from this problem is that when dealing with products, "bad" values (large negatives) can become "good" values later. By tracking both boundaries (min and max), we ensure we never miss a potential solution.