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 sum 1600
 

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

 


 
The idea is very simple. We maintain two variables to store the maximum and minimum product ending at current position. For 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 🙂