Find maximum product subarray in a given array


Given an array of integers, find maximum product subarray. In other words, find a sub-array that has maximum product of its elements.

 

For example,


Input:  { -6, 4, -5, 8, -10, 0, 8 }

Output: The maximum product sub-array is {4, -5, 8, -10} having product 1600
 

Input:  { 40, 0, -20, -10 }

Output: The maximum product sub-array is {-20, -10} having product 200

 
Naive solution would be to consider every sub-array and find product of their elements. Finally, we return the maximum product found among all sub-arrays. The implementation can be seen here. The time complexity of this solution is O(n2).

A better solution will be to maintain two variables to store the maximum and minimum product ending at current position. Then we traverse the array once and for every index i in the array, we update maximum and minimum product ending at A[i]. We update the result if maximum product ending at any index if more than maximum product found so far.

C

Download   Run Code

Output:

The maximum product of a sub-array is 1600

Java

Download   Run Code

Output:

The maximum product of a sub-array is 1600

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Andrew
Guest

Hi. This solution works for array+subarray. I think we should consider the case of unordered set+subset as well.
Best.

Tarun Mitra
Guest

If let’s say the array is just { -6 } then this algorithm will result in 0 but I am assuming it should be -6. is that correct?

Tony
Guest

Yep! We need to explicitly handle the case when size of the input array is 1.