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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    //本题的思想为动态规划
    //定义一个一样长的node类型的dp数组
    //dp[i]有两个值，dp[i].max的含义为必须以nums[i]为结尾的情况下连续子数组的最大值
    //dp[i].min的含义为必须以nums[i]为结尾的情况下，连续子数组的最小值
    //为什么要求最小值，比如实例3，-2*-6的结果反而是最大的,这就是为什么要求最小值的原因
    //用一个变量res统计求dp数组的过程中出现的最大值即可
    struct node{
        int max;
        int min;
    };
    int max(int a,int b){
        return a>b?a:b;
    }
    int min(int a,int b){
        return a>b?b:a;
    }
    int maxProduct(vector<int>& nums) {
        // write code here
        if(nums.size()<=0)
            return 0;
        int n=nums.size();
        node dp[n];
        dp[0].max=nums[0];
        dp[0].min=nums[0];
        int res=dp[0].max;
        for(int i=1;i<n;i++){
            dp[i].max=max(max(nums[i]*dp[i-1].max,nums[i]*dp[i-1].min),nums[i]);
            dp[i].min=min(min(nums[i]*dp[i-1].max,nums[i]*dp[i-1].min),nums[i]);
            res=max(res, dp[i].max);
        }
        return res;
    }
};