9. Maximum Product Subarray

Description

Maximum Product Subarray

Given an integer array nums, find a that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

• 1 <= nums.length <= 2 * 104
• -10 <= nums[i] <= 10
• The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Approach

• Use prefix and suffix product, the way it moves from both side it seems to ensure to cover all subarrays
• If we encounter a zero then set prefix and suffix as 1

class Solution {
    public int maxProduct(int[] nums) {
        int p = 1, s = 1;
        int m = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (p == 0) p = 1;
            if (s == 0) s = 1;
            p *= nums[i];
            s *= nums[nums.length - i - 1];
            m = Math.max(m, Math.max(p,s));
        }
        return m;
    }
}

Primary Approach: Dynamic Programming (Tracking Min and Max Products) ($O(N)$ Time, $O(1)$ Space)

Intuition

Unlike 53. Maximum Subarray, multiplying two negative numbers yields a positive number. Therefore, a very small negative product can suddenly become the largest positive product if multiplied by another negative number.

1. At each element nums[i], maintain two running values:
   • currMax: The maximum product of a subarray ending at index i.
   • currMin: The minimum product of a subarray ending at index i.
2. When nums[i] is negative, multiplying by currMax yields a smaller number, while multiplying by currMin yields a larger number. Thus, swap currMax and currMin before calculating updates.
3. Update values:
   • currMax = max(nums[i], currMax * nums[i])
   • currMin = min(nums[i], currMin * nums[i])
4. Update global maxProduct with currMax at each step.

class Solution {
    public int maxProduct(int[] nums) {
        int result = nums[0];
        int currMax = nums[0];
        int currMin = nums[0];
 
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
 
            // Multiplying by a negative flips max to min and min to max
            if (num < 0) {
                int temp = currMax;
                currMax = currMin;
                currMin = temp;
            }
 
            currMax = Math.max(num, currMax * num);
            currMin = Math.min(num, currMin * num);
 
            result = Math.max(result, currMax);
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Single pass through array of length $N$.
• Space Complexity: $O(1)$ auxiliary space — Only uses $O(1)$ extra variables (currMax, currMin, result).

---

Alternative Approach: Prefix & Suffix Product Traversal ($O(N)$ Time, $O(1)$ Space)

Intuition

Consider the properties of array products:

1. If an array contains no zeros and an even number of negative values, the maximum product is the product of all elements.
2. If an array contains an odd number of negative values, removing either the prefix ending at the first negative number or the suffix starting at the last negative number leaves an even count of negative numbers.
3. If 0 is encountered, it resets any product chain to 1.
   Thus, computing the prefix product (left to right) and suffix product (right to left) simultaneously guarantees covering the optimal subarray boundary.

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        long prefix = 1;
        long suffix = 1;
        long maxProd = Long.MIN_VALUE;
 
        for (int i = 0; i < n; i++) {
            if (prefix == 0) prefix = 1;
            if (suffix == 0) suffix = 1;
 
            prefix *= nums[i];
            suffix *= nums[n - 1 - i];
 
            maxProd = Math.max(maxProd, Math.max(prefix, suffix));
        }
 
        return (int) maxProd;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Single loop running $N$ iterations to calculate prefix and suffix products.
• Space Complexity: $O(1)$ auxiliary space.

---

Key Interview Discussion Points

• Why standard Kadane’s Algorithm fails: Basic Kadane’s algorithm assumes local subproblems are monotonic (larger values stay larger). With negative numbers, a negative product can flip into a maximum positive product on the next negative element.
• Handling Zeros: Any zero encountered forces local subarray product candidates to reset. Both $O(1)$ DP and Two-Pointer (Prefix/Suffix) approaches handle 0 by resetting running products to $1$.

---

Easy Memory Rule

“Negative flips sign $\to$ Track both currMax AND currMin (or compute Left-to-Right and Right-to-Left products)!”