Maximum Product Subarray

Problem: Find the contiguous sub-array within an array which has the largest product.

Solution: When the array has only positive elements then the product of all elements will be answer but when there are negative elements the problem becomes a bit complex. Following are the steps for solving this problem -

1. If current element is positive then max product can be achieved by multiplying current element with max product calculated so far.
2. If current element is negative then max product can be achieved by multiplying current element with min product calculated so far.
3. Current element might be a starting position for max product sub-array.

Implementation:

int maxProductSubArray(int *arr, int len)

{

if(arr == NULL || len == 0)

return 0;

if(len == 1)

return arr[0];

int prevMax = arr[0], prevMin = arr[0];

int maxProduct = arr[0];

for(int i = 1; i < len; ++i)

{

int currMax = max3(prevMax * arr[i], prevMin * arr[i], arr[i]);

int currMin = min3(prevMax * arr[i], prevMin * arr[i], arr[i]);

maxProduct = max(maxProduct, currMax);

prevMax = currMax;

prevMin = currMin;

}

return maxProduct;

}

Complexity: O(n)