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