152 Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.


Solution: Dynamic Programming

Similiar to 53 Maximum Subarray

3 things to consider:

  1. min/maxProduct [i]
  2. min/maxProduct [i-1]
  3. A[i]

The trick is:

  1. When the smallest negative number meet another negative number, it might be the largest product.
  2. When the largest positive number meet a negative number it's going to be very small

So we need to keep track two types of products throught the way:

  • minProduct = min(minProduct[i-1]A[i], maxProduct[i-1]A[i], A[i]);
  • maxProduct = max(maxProduct[i-1]A[i], minProduct[i-1]A[i], A[i]);
public int maxProduct(int[] nums) {

    if (nums==null)
    {
        return 0;
    }

    int res, curMin, curMax;
    res = curMin = curMax = nums[0];
    for(int i=1; i<nums.length; i++)
    {
       int tempMax = curMax;
       curMax = Math.max(Math.max(curMax*nums[i], curMin*nums[i]), nums[i]);
       curMin = Math.min(Math.min(curMin*nums[i], tempMax*nums[i]), nums[i]);

       res = Math.max(res, curMax);
    }
    return res;
}

results matching ""

    No results matching ""