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).

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Andrew
Guest
Andrew

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

Tarun Mitra
Guest
Tarun Mitra

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
Tony

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