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[0]); //size of the array
    maxProduct(arr, n);
    return 0;
}
Try It


Next > < Prev
Scroll to Top