Maximum Product Subarray

---

Maximum Product Subarray: Given an integer array nums, find a subarray 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 * 10^4
• -10 <= nums[i] <= 10
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

---

Try this Problem on your own or check similar problems:

1. Product of Array Except Self
2. House Robber
3. House Robber II

Solution:

Java

public int maxProduct(int[] nums) {
    int minProduct = 1, maxProduct = 1;
    int bestSoFar = Integer.MIN_VALUE;

    for(int num: nums){
        if(num < 0){
            int temp = minProduct;
            minProduct = maxProduct;
            maxProduct = temp;
        }

        minProduct = Math.min(num, num * minProduct);
        maxProduct = Math.max(num, num * maxProduct);

        bestSoFar = Math.max(bestSoFar, maxProduct);
    }

    return bestSoFar;
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
  let minProduct = 1;
  let maxProduct = 1;
  let bestSoFar = Number.MIN_SAFE_INTEGER;

  for (let num of nums) {
    if (num < 0) {
      let temp = minProduct;
      minProduct = maxProduct;
      maxProduct = temp;
    }

    minProduct = Math.min(num, num * minProduct);
    maxProduct = Math.max(num, num * maxProduct);

    bestSoFar = Math.max(bestSoFar, maxProduct);
  }

  return bestSoFar;
};

Python

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        minProduct = 1
        maxProduct = 1
        bestSoFar = float('-inf')

        for num in nums:
            if num < 0:
                minProduct, maxProduct = maxProduct, minProduct

            minProduct = min(num, num * minProduct)
            maxProduct = max(num, num * maxProduct)

            bestSoFar = max(bestSoFar, maxProduct)

        return bestSoFar

C++

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int minProduct = 1;
        int maxProduct = 1;
        int bestSoFar = INT_MIN;

        for (int num : nums) {
            if (num < 0) {
                swap(minProduct, maxProduct);
            }

            minProduct = min(num, num * minProduct);
            maxProduct = max(num, num * maxProduct);

            bestSoFar = max(bestSoFar, maxProduct);
        }

        return bestSoFar;
    }
};

---

Time/Space Complexity:

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

---

Explanation:

Think of it as keeping track of local minimum and maximum. For each number in the array, we update the maxProduct we have seen so far which can be either just that num or the product of the maxProduct and num, same goes for the minProduct except that we're trying to minimize it. Best result it's either bestSoFar or maxProduct, notice that we have negative numbers in the input array too, so we have switch the maxProduct and minProduct (e.g. we have maxProduct = 100 and minProduct = -30, and num = -2, then the maxProduct would switch to -200, but the minProduct would switch to 60). We're trying to maximize the product for each of the elements that's why it's good to multiply the minProduct which has the largest absolute value so far with the negative number we have since that would turn it into a large positive value. Finally, we return bestSoFar.