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; }