题解 | #子数组最大乘积#

随手记录下解题过程，各位看官将就看下吧--------
这个题目其实是要求【连续】子数组，一开始理解错了，一直没通过
实际代码没有用dp数组，采用【滚动数组】思想（可以参考leetcode152），用两个变量保存最大和最小值，因为当前最值只和上一个最值有关

// NC83子数组最大乘积
/*     状态定义：
    dp_max[i]:以下标为i的【连续】子数组的最大乘积
    dp_min[i]:以下标为i的【连续】子数组的最小乘积
    状态转移：
        arr[i]>0时，希望上一次的乘积尽可能大，正*正=正，乘积才能尽可能大；
        arr[i]<=0时，希望上一次的乘积尽可能小，负*负=正，乘积才能尽可能大；
        方程式：
            dp_max[i]=max(arr[i],dp_max[i-1]*arr[i]);//(arr[i]>0)
            dp_min[i]=min(arr[i],dp_min[i-1]*arr[i]);//(arr[i]>0)

            dp_max[i]=max(arr[i],dp_min[i-1]*arr[i]);//(arr[i]<=0)
            dp_min[i]=min(arr[i],dp_max[i-1]*arr[i]);//(arr[i]<=0)
    返回结果：
        每次子数组长度+1，就判断当前长度下最大的乘积。最后返回最大的即可。

     */

class Solution {
public:
    double maxProduct(vector<double> arr) {
        int len=arr.size();
        vector<int>dp(len);
        if(len==0) return 0;
        if(len==1) return arr[0];
        // 初始化
        double max_num=arr[0];//最大乘积
        double min_num=arr[0];//最小乘积
        double ret=max_num;//返回值，注意是double类型
        // 循环
        // dp[0]=arr[0];
        for(int i=1;i<len;++i){
            if(arr[i]>0){
                max_num=max( arr[i],arr[i]*max_num);
                min_num=min( arr[i],arr[i]*min_num);
            }else{
                double tmp_max=max_num;
                double tmp_min=min_num;
                max_num=max(arr[i],arr[i]*tmp_min);
                //此处求min的时候不能直接使用max_num，该max_num是最新的，而不是上次的
                // min_num=min(arr[i],arr[i]*max_num);  错误！！
                min_num=min(arr[i],arr[i]*tmp_max);//正确
            }
            ret=max(ret,max_num);
        }
        return ret;
    }
};