# 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`.

Thoughts:

Since two negative numbers multiply could result in positive, here we need to have two arrays, dmax, dmin to keep track of max product and min product so far

Code

``````class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
if(n == 1) return nums[0];
int maxP = nums[0];

for(int i  = 1, dmin = nums[0], dmax = nums[0]; i < n; i++){
if(nums[i] < 0)
swap(dmin, dmax);

dmin = min(nums[i], dmin*nums[i]);
dmax = max(nums[i], dmax*nums[i]);

maxP = maxP > dmax? maxP: dmax;
}

return maxP;
}
};
``````
``````class Solution {
public int maxProduct(int[] nums) {
if(nums == null && nums.length == 0) return 0;
// initial value
int max = nums[0], min = nums[0], ans = nums[0];
for (int i = 1; i < nums.length; i++){
int prevMin = min, prevMax = max;
max = Math.max(nums[i], Math.max(prevMin * nums[i], prevMax * nums[i]));
min = Math.min(nums[i], Math.min(prevMin * nums[i], prevMax * nums[i]));
// update results
ans = Math.max(ans, max);
}
return ans;
}
}
``````