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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param nums int整型vector 
     * @return int整型
     */
    int maxProduct(vector<int>& nums) {
        vector<int> pos(nums); // 存储以nums[i] 结尾的最大乘积
        vector<int> neg(nums); // 存储以 nums[i] 结尾的最小乘积
        int result=nums[0];
        for(int i=1;i<nums.size();i++){
            pos[i]=max(nums[i],max(nums[i]*pos[i-1],nums[i]*neg[i-1]));
            neg[i]=min(nums[i],min(nums[i]*pos[i-1],nums[i]*neg[i-1]));
            result=max(result,pos[i]);
        }
        return result;
    }
};

用数组pos[i]和neg[i]分别存储以num[i] 为结尾的子数组的最大乘积和最小乘积。pos和neg的初始值都是nums数组。

更新时，pos[i] 取 nums[i], nums[i]*pos[i-1], nums[i]*neg[i-1] 的最大值。neg[i] 取他们三个的最小值。

每次都比较pos[i] 和最终结果的关系，取最大的那个作为最终结果。