LeetCode 152. 乘积最大子数组

LeetCode 152. 乘积最大子数组

思路：
Dp 滚动数组
f[i] 记录以i为结尾的子段最大的数值。
g[i] 记录以i为结尾的子段最小的数字。
这样做的原因是乘法求最大，可能全是整数，也可能全是负数。
对于f[i]来说可能有以下三种情况：

1. 只有nums[i]
2. nums[i] > 0 f[i] = f[i - 1] * nums[i]
3. nums[i] < 0 f[i] = g[i - 1] * nums[i]
   同理g数组也是一样的
   但是我们这里可以不用对于每个数组都去枚举，无脑求出三种情况，然后最大的是f[i] ，最小的是g[i]

代码：

class Solution {
public:
    //最小
    vector<int> f;
    //最大
    vector<int> g;
    int maxProduct(vector<int>& nums) {
        //Dp
        //滚动数组
        int n = nums.size();
        f = vector<int> (2);
        g = vector<int> (2);
        f[0] = nums[0],g[0] = nums[0];
        int res = nums[0];
        for(int i = 1;i < n;i++){
            int a = nums[i];
            f[i & 1] = max(a,max(f[i - 1 & 1] * a,g[i - 1 & 1] * a));
            g[i & 1] = min(a,min(f[i - 1 & 1] * a,g[i - 1 & 1] * a));
            res = max(res,f[i & 1]);
        }
        return res;
    }
};