Home » 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.


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

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


  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;
		return num2;
int min(int num1, int num2)
		return num1;
		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;

READ  Finding K closest element

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions