Home » Technical Interview Questions » Array Interview Questions » Maximum product subarray

# Maximum product subarray

## Given an array consisting of positive, negative integers and also zeroes, this function will find  the maxium product of the subarray.

### Example

INPUT:
arr[] = {3, -6, -1, 0, 4}

OUTPUT:
Maximum product is 18
Subarray {3, -6, -1} is having the maximum product

Time Complexity: O(n)

The main idea in this method is taking two variables localmin,  localmax and keep track of minimum negative value and maximum positive value

## Algorithm

1. Traverse the array, if the element is positive, then make localmax = localmax * arr[i], localmin = min(localmin*arr[i], 1).
2. If the element is negative, then store localmax value in t variable and update the localmax value to maximum of (localmin* arr[i], 1), and update the localmin to t * arr[i].
3. If the element is zero, then make localmax and localmin equal to 1.
4. update the maxproduct(which is the maximum product till now) if it is less than present subarray product(localmax).
5. return maxproduct ## C++ Program

```#include <bits/stdc++.h>
using namespace std;

int max(int num1, int num2)
{
if (num1>num2)
{
return num1;
}
else
return num2;
}
int min(int num1, int num2)
{
if(num1<num2)
{
return num1;
}
else
return num2;
}
int maxProduct(int arr[], int n)
{
int localmin=1, localmax=1;//localmax is maximum +ve integer
int maxproduct =0;			//localmin is least -ve integer
for (int i = 0; i < n; ++i)
{
if( arr[i]>0) //if the element is greater than 0
{				//product previous max to the element
localmax = localmax * arr[i];
localmin = min(localmin*arr[i],1);
}
else if(arr[i]==0)
{
localmax = 1;
localmin = 1;
}
else  //if the element is negative
{
int t = localmax;
localmax = max(localmin * arr[i], 1);
localmin = t * arr[i];
}
if(localmax > maxproduct)
{
maxproduct = localmax;
}
}
cout<<"Maximum product is "<<maxproduct;
}
int main()
{

int arr[]= {3, -6, -1, 0, 4};  //creating an array
int n = sizeof(arr)/sizeof(arr); //size of the array
maxProduct(arr, n);
return 0;
}```

READ  Count minimum steps to get the given desired array
 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions