# Maximum Product Subarray

#### Maximum Product Subarray

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

Example

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

Solution: One Pass O(n) time.

So for each index i, max(i) = the maximum product ending at i, so we have

max(i) = max(max(i-1)*nums[i], nums[i]) //nums[i]>=0

since you can either append from the previous one, or just start a new contiguous subarray.

Be careful on negative nums, if nums[i] < 0, the equation now becomes:

max(i) = max(min(i-1)*nums[i], nums[i]) //nums[i]<0

```public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int maxProduct = Integer.MIN_VALUE;
int preMax = 1;
int preMin = 1;
for (int i = 0; i < nums.length; i++) {
int max, min;
if (nums[i] >= 0) {
max = Math.max(preMax * nums[i], nums[i]);
min = Math.min(preMin * nums[i], nums[i]);
} else {
max = Math.max(preMin * nums[i], nums[i]);
min = Math.min(preMax * nums[i], nums[i]);
}
maxProduct = Math.max(maxProduct, max);
preMax = max;
preMin = min;
}
return maxProduct;
}```
Share