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:
- min/maxProduct [i]
- min/maxProduct [i-1]
- A[i]
The trick is:
- When the smallest negative number meet another negative number, it might be the largest product.
- 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;
}