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.
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)
HOW TO ARRAY ELEMENT WHICH CONTRIBUTED TO MAX PRODUCT.
ReplyDeleteeg- 10 -2 -3 -30 100
o/p- -3 -30 100
We need to maintain the start and end point in the loop.
DeleteWrong out put for {-1,2,-3} and {-1,-2,3} gives output as 6
ReplyDeletewhich is wrong, correct is 3 and 2 respectively.
Amit,
DeleteOutput is 6 in both of the above cases. For 1st it is -1 X 2 X -3 = 6
and for 2nd -1 X -2 X 3 = 6.
In both of the cases the whole elements of the array are involved in the product.
wrong output for arr[] = {1, -2, -3, 0, 7, -8, -2,2,2};
ReplyDeletehttps://ideone.com/ePoigA
Hi Shantanu,
DeleteIt is giving right result - 448 which is correct.
I saw your code and found that your max3 and min3 definitions are incorrect. Please use following definitions for max3 and min3
int max3(int a, int b, int c)
{
return a > b ? (a > c ? a : c) : (b > c ? b : c);
}
int min3(int a, int b, int c)
{
return a < b ? (a < c ? a : c) : (b < c ? b : c);
}
You can convert it into your if - else form. Hope it will help