Find maximum product subarray in a given array


Given an array of integers, find sub-array in it 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++ implementation –
 

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 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Andrew
Guest
Andrew

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

wpDiscuz