Monday, May 4, 2015

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)

6 comments:

  1. HOW TO ARRAY ELEMENT WHICH CONTRIBUTED TO MAX PRODUCT.
    eg- 10 -2 -3 -30 100
    o/p- -3 -30 100

    ReplyDelete
    Replies
    1. We need to maintain the start and end point in the loop.

      Delete
  2. Wrong out put for {-1,2,-3} and {-1,-2,3} gives output as 6
    which is wrong, correct is 3 and 2 respectively.

    ReplyDelete
    Replies
    1. Amit,
      Output 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.

      Delete
  3. wrong output for arr[] = {1, -2, -3, 0, 7, -8, -2,2,2};
    https://ideone.com/ePoigA

    ReplyDelete
    Replies
    1. Hi Shantanu,
      It 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

      Delete