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



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


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 🙂