Given an array of integers, find maximum product subarray. In other words, find a sub-array that has maximum product of its elements.

**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(n^{2}).

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> using namespace std; // Function to return maximum product of a sub-array of given array int maxProduct(int arr[], int n) { // maintain two variables to store maximum and minimum product // ending at current index int max_ending = 0, min_ending = 0; // to store maximum product sub-array found so far int max_so_far = 0; // traverse the given array for (int i = 0; i < n; i++) { int temp = max_ending; // update maximum product ending at current index max_ending = max(arr[i], max(arr[i] * max_ending, arr[i] * min_ending)); // update minimum product ending at current index min_ending = min(arr[i], min(arr[i] * temp, arr[i] * min_ending)); max_so_far = max(max_so_far, max_ending); } // return maximum product return max_so_far; } // main function int main() { int arr[] = { -6, 4, -5, 8, -10, 0, 8 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "The maximum product of a sub-array is " << maxProduct(arr, n); return 0; } |

`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

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

Best.

Andrew, we have published this problem as well –

http://www.techiedelight.com/maximum-product-subset-problem/