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

(1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Subscribe
Notify of
Guest

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

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