C++ Program for Maximum Product Subarray

Last Updated : 23 Jul, 2025

Given an array that contains both positive and negative integers, find the product of the maximum product subarray. Expected Time complexity is O(n) and only O(1) extra space can be used.

Examples:

Input: arr[] = {6, -3, -10, 0, 2} Output: 180 // The subarray is {6, -3, -10} Input: arr[] = {-1, -3, -10, 0, 60} Output: 60 // The subarray is {60} Input: arr[] = {-2, -40, 0, -2, -3} Output: 80 // The subarray is {-2, -40}

Naive Solution:

The idea is to traverse over every contiguous subarrays, find the product of each of these subarrays and return the maximum product from these results.

Below is the implementation of the above approach.

C++

// C++ program to find Maximum Product Subarray #include <bits/stdc++.h> using namespace std; /* Returns the product of max product subarray.*/ int maxSubarrayProduct(int arr[], int n) {  // Initializing result  int result = arr[0];  for (int i = 0; i < n; i++)   {  int mul = arr[i];  // traversing in current subarray  for (int j = i + 1; j < n; j++)   {  // updating result every time  // to keep an eye over the maximum product  result = max(result, mul);  mul *= arr[j];  }  // updating the result for (n-1)th index.  result = max(result, mul);  }  return result; } // Driver code int main() {  int arr[] = { 1, -2, -3, 0, 7, -8, -2 };  int n = sizeof(arr) / sizeof(arr[0]);  cout << "Maximum Sub array product is "  << maxSubarrayProduct(arr, n);  return 0; } // This code is contributed by yashbeersingh42

Output:

Maximum Sub array product is 112

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Solution:

The following solution assumes that the given input array always has a positive output. The solution works for all cases mentioned above. It doesn't work for arrays like {0, 0, -20, 0}, {0, 0, 0}.. etc. The solution can be easily modified to handle this case.
It is similar to Largest Sum Contiguous Subarray problem. The only thing to note here is, maximum product can also be obtained by minimum (negative) product ending with the previous element multiplied by this element. For example, in array {12, 2, -3, -5, -6, -2}, when we are at element -2, the maximum product is multiplication of, minimum product ending with -6 and -2.

C++

// C++ program to find Maximum Product Subarray #include <bits/stdc++.h> using namespace std; /* Returns the product   of max product subarray. Assumes that the given  array always has a subarray with product more than 1 */ int maxSubarrayProduct(int arr[], int n) {  // max positive product   // ending at the current position  int max_ending_here = 1;  // min negative product ending   // at the current position  int min_ending_here = 1;  // Initialize overall max product  int max_so_far = 0;  int flag = 0;  /* Traverse through the array.   Following values are  maintained after the i'th iteration:  max_ending_here is always 1 or   some positive product ending with arr[i]  min_ending_here is always 1 or   some negative product ending with arr[i] */  for (int i = 0; i < n; i++)  {  /* If this element is positive, update  max_ending_here. Update min_ending_here only if  min_ending_here is negative */  if (arr[i] > 0)   {  max_ending_here = max_ending_here * arr[i];  min_ending_here  = min(min_ending_here * arr[i], 1);  flag = 1;  }  /* If this element is 0, then the maximum product  cannot end here, make both max_ending_here and  min_ending_here 0  Assumption: Output is always greater than or equal  to 1. */  else if (arr[i] == 0) {  max_ending_here = 1;  min_ending_here = 1;  }  /* If element is negative. This is tricky  max_ending_here can either be 1 or positive.  min_ending_here can either be 1 or negative.  next max_ending_here will always be prev.  min_ending_here * arr[i] ,next min_ending_here  will be 1 if prev max_ending_here is 1, otherwise  next min_ending_here will be prev max_ending_here *  arr[i] */  else {  int temp = max_ending_here;  max_ending_here  = max(min_ending_here * arr[i], 1);  min_ending_here = temp * arr[i];  }  // update max_so_far, if needed  if (max_so_far < max_ending_here)  max_so_far = max_ending_here;  }  if (flag == 0 && max_so_far == 0)  return 0;  return max_so_far; } // Driver code int main() {  int arr[] = { 1, -2, -3, 0, 7, -8, -2 };  int n = sizeof(arr) / sizeof(arr[0]);  cout << "Maximum Sub array product is "  << maxSubarrayProduct(arr, n);  return 0; } // This is code is contributed by rathbhupendra