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

Output:

The maximum product of a sub-array is 1600

Java

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

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

Subscribe
Notify of
Guest
Andrew

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

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?

Guest
Tony

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