# 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.
# Solution
Approach 1: DP.
# Code (Python)
Approach 1:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return 0
max_product = nums[0]
min_product = nums[0]
global_max = nums[0]
for num in nums[1:]:
temp = max_product * num
max_product = max(temp, num, min_product * num)
min_product = min(temp, num, min_product * num)
global_max = max(global_max, max_product)
return global_max
# Code (C++)
Approach 1:
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
int maxOfAll = nums[0];
int prevMax = nums[0];
int prevMin = nums[0];
for (int i = 1; i < n; ++i)
{
/*
int wPrevMax = prevMax * nums[i];
int wPrevMin = prevMin * nums[i];
int currMax = std::max(std::max(wPrevMax, wPrevMin), nums[i]);
int currMin = std::min(std::min(wPrevMax, wPrevMin), nums[i]);
*/
int currMax;
int currMin;
if (nums[i] >= 0)
{
currMax = std::max(nums[i], nums[i] * prevMax);
currMin = std::min(nums[i], nums[i] * prevMin);
}
else
{
currMax = std::max(nums[i], nums[i] * prevMin);
currMin = std::min(nums[i], nums[i] * prevMax);
}
maxOfAll = std::max(maxOfAll, currMax);
prevMax = currMax;
prevMin = currMin;
}
return maxOfAll;
}
};