0%

LeetCode: 152. Maximum Product Subarray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxProduct(vector<int>& nums) {
if(nums.empty())
return 0;
vector<int> f(nums.size()), g(nums.size());
int ret = f[0]=g[0]=nums[0];
for(int i=1;i<nums.size();++i)
{
f[i]=max(nums[i], max(g[i-1]*nums[i], f[i-1]*nums[i]));
g[i]=min(nums[i], min(g[i-1]*nums[i], f[i-1]*nums[i]));
ret = max(f[i], ret);
}
return ret;
}
};