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

线性DP

设pos[i]为以i为结尾的子数组的最大乘积，neg[i]为以i为结尾的子数组的最小乘积，状态转移方程见代码。 时间复杂度：$O(n)O(n)$ 空间复杂度：$O(n)O(n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int maxProduct(vector<int>& nums) {
        // write code here
        int n = nums.size();
        vector<int> pos(n), neg(n);
        pos[0] = neg[0] = nums[0];
        for(int i = 1; i < n; i ++){
            if(nums[i] >= 0){
                pos[i] = max(pos[i - 1] * nums[i], nums[i]);
                neg[i] = min(neg[i - 1] * nums[i], nums[i]);
            }else{
                pos[i] = max(neg[i - 1] * nums[i], nums[i]);
                neg[i] = min(pos[i - 1] * nums[i], nums[i]);
            }
        }
        int ans = INT_MIN;
        for(int i = 0; i < n; i ++){
            ans = max(ans, pos[i]);
        }
        return ans;
    }
};