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
- Traverse the array, if the element is positive, then make localmax = localmax * arr[i], localmin = min(localmin*arr[i], 1).
- 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].
- If the element is zero, then make localmax and localmin equal to 1.
- update the maxproduct(which is the maximum product till now) if it is less than present subarray product(localmax).
- 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[0]); //size of the array
maxProduct(arr, n);
return 0;
}