Maximum Product Subarray

Given an array arr[] that contains positive and negative integers (may contain 0 as well). Find the maximum product that we can get in a subarray of arr.

Note: It is guaranteed that the output fits in a 32-bit integer.

Examples

Input: arr[] = [-2, 6, -3, -10, 0, 2]
Output: 180
Explanation: The subarray with maximum product is {6, -3, -10} with product = 6 * (-3) * (-10) = 180.

Input: arr[] = [-1, -3, -10, 0, 60]
Output: 60
Explanation: The subarray with maximum product is {60}.

Input: arr[] = [2, 3, 4] 
Output: 24 
Explanation: For an array with all positive elements, the result is product of all elements. 

Constraints:
1 ≤ arr.size() ≤ 10⁶
-10 ≤ arr[i] ≤ 10

Approach 01:

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
 public:
  int maxProduct(vector<int>& nums) {
    int startIndex = 0, endIndex = 0;
    int arrayLength = nums.size();
    int currentProduct = 1;
    int maxProduct = INT_MIN;

    while (endIndex < arrayLength) {
      if (nums[endIndex] == 0)
        maxProduct = max(maxProduct, 0);

      if (nums[endIndex] != 0) {
        currentProduct *= nums[endIndex];
        maxProduct = max(maxProduct, currentProduct);
        endIndex++;
      } else {
        while (startIndex < endIndex - 1) {
          currentProduct /= nums[startIndex];
          maxProduct = max(maxProduct, currentProduct);
          startIndex++;
        }
        endIndex++;
        startIndex = endIndex;
        currentProduct = 1;
      }
    }

    while (startIndex < endIndex - 1) {
      currentProduct /= nums[startIndex];
      maxProduct = max(maxProduct, currentProduct);
      startIndex++;
    }

    return maxProduct;
  }
};

class Solution:
    # Function to find maximum product subarray
    def maxProduct(self, nums):
        startIndex, endIndex = 0, 0
        arrayLength = len(nums)
        currentProduct = 1
        maxProduct = -float("inf")

        while endIndex < arrayLength:
            if nums[endIndex] == 0:
                maxProduct = max(maxProduct, 0)

            if nums[endIndex] != 0:
                currentProduct *= nums[endIndex]
                maxProduct = max(maxProduct, currentProduct)
                endIndex += 1
            else:
                while startIndex < endIndex - 1:
                    currentProduct //= nums[startIndex]
                    maxProduct = max(maxProduct, currentProduct)
                    startIndex += 1
                endIndex += 1
                startIndex = endIndex
                currentProduct = 1

        while startIndex < endIndex - 1:
            currentProduct //= nums[startIndex]
            maxProduct = max(maxProduct, currentProduct)
            startIndex += 1

        return maxProduct

Time Complexity

• Outer While Loop:

  The loop iterates through each element of the array once, so the time complexity is \( O(n) \), where \( n \) is the size of the input array.

• Inner While Loop:

  The inner loop, which runs when encountering a zero, processes a subset of the array. Each element is processed at most twice (once in the outer loop and potentially once in the inner loop), so the overall complexity remains \( O(n) \).

• Operations Per Element:

  Operations such as multiplication, division, and updating the maximum product are \( O(1) \), so they do not affect the overall complexity.

• Overall Time Complexity:

  The total time complexity is \( O(n) \).

Space Complexity

• Variables:

  The function uses a constant number of scalar variables: startIndex, endIndex, arrayLength, currentProduct, and maxProduct, which require \( O(1) \) space.

• Input Array:

  The input array nums is not modified or duplicated, so it does not contribute to additional space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \), as no additional data structures are used.