class Solution {
public:
int maxProduct(vector<int>& nums) {
// dp[j] 截止到nums[j]的乘积最大的非空连续子数组的乘积
std::vector<int> dpmin(nums.size()), dpmax(nums.size());
dpmax[0] = nums[0], dpmin[0]= nums[0];
int res = nums[0];
for (int j=1; j<nums.size();j++){
dpmin[j] = std::min(std::min(dpmin[j-1]*nums[j], dpmax[j-1]*nums[j]), nums[j]);
dpmax[j] = std::max(std::max(dpmin[j-1]*nums[j], dpmax[j-1]*nums[j]), nums[j]);
res = std::max(res, dpmax[j]);
}
return res;
}
};