0%

LeetCode: 152. Maximum Product Subarray

Posted on Edited on In , Valine: 
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;
    }
};