题解 | 连续子数组的最大乘积

#include <type_traits>
class Solution {
public:
    //可以用一个二维数组记录记录从哪到哪儿的乘积是多少，并用一个变量记录最大值
    //按道理，正数肯定是越乘越大，就是有0 或者负数的存在，我们不知道下一个是正数还是负数还是0，也很难知道之前有多少的负数0，
    //正数肯定和正数乘最大，但是后面可能有负数，和负数的乘也应该保留，但是保留多少负数的参与呢？
    //采用保存以此结尾的最大和最小乘积，更新时这个数乘以最大和最小，正数乘最大正数得，负数乘前面最小负数，但是在乘的时候必须保存最大和最小
    int maxProduct(vector<int>& nums) {
        vector<int> pos(nums);
        vector<int> neg(nums);
        int res = nums[0];

        for(int i=1; i<nums.size(); ++i){
            pos[i] = max(nums[i], max( pos[i-1]*nums[i], neg[i-1]*nums[i]) );
            neg[i] = min(nums[i], min( pos[i-1]*nums[i], neg[i-1]*nums[i]) );

            res = max(res, pos[i]);
        }

        return res;
    }
};