# LeetCode Maximum Product Subarray

152. Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.


Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

curMax = max(curMax*nums[i], curMin*nums[i], nums[i]);
curMin = min(curMax*nums[i], curMin*nums[i], nums[i]);

class Solution {
public: int maxProduct(vector < int > & nums) {
int ans = nums[0], curMax = nums[0], curMin = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
int tmp = curMax;
curMax = max(max(curMax * nums[i], curMin * nums[i]), nums[i]);
curMin = min(min(tmp * nums[i], curMin * nums[i]), nums[i]);
ans = max(ans, curMax);
}
return ans;
}
};

class Solution {
public: int maxProduct(vector < int > & nums) {
int ans = nums[0], curMax = 1, curMin = 1;
for (size_t i = 0; i < nums.size(); ++i) {
int oldMax = max(curMax, 1);
if (nums[i] > 0) {
curMax = oldMax * nums[i];
curMin *= nums[i];
} else {
curMax = curMin * nums[i];
curMin = oldMax * nums[i];
}
ans = max(ans, curMax);
}
return ans;
}
};