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 -
- If current element is positive then max product can be achieved by multiplying current element with max product calculated so far.
- If current element is negative then max product can be achieved by multiplying current element with min product calculated so far.
- Current element might be a starting position for max product sub-array.
int maxProductSubArray(int *arr, int len)
if(arr == NULL || len == 0)
if(len == 1)
int prevMax = arr, prevMin = arr;
int maxProduct = arr;
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;