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

题目描述
给定一个double类型的数组arr，其中的元素可正可负可0，返回子数组累乘的最大乘积。

方法一：暴力求解

求解思路
对于求解子数组的最大乘积，只需要按照子数组的大小，进行遍历，最后记录最大乘积，输出结果即可。

图片说明

解题代码

class Solution {
public:
    double maxProduct(vector<double> arr) {
        double myres = arr[0];
        for (int i = 0; i < arr.size(); i++) {//外层循环
            double mul = 1;
            for (int j = i; j < arr.size(); j++) {//内层循环
                mul *= arr[j];
                myres = max(myres, mul);//这个地方就是两层循环，然后直接求解最大值。
            }
        }
        return myres;
    }
};

复杂度分析
时间复杂度：两层循环，所以时间复杂度为 $图片说明$
空间复杂度：没有引入额外的地址空间，因此为 $O(1)$

方法二：动态规划

求解思路
对于本题要求解子数组的最大乘积，我们参考求解子数组最大和的思想，将状态转移方程改为：
图片说明
其中fmax是当前状态的最大值，fmin是当前状态的最小值。因为本题目是求解子数组最大乘积，我们考虑到负数乘负数得到正数，此时有可能会比连续正数相乘的值大，所以我们记录每个状态的最大值和最小值，并且和当前arr[i]的值进行对比，最终得到子数组的最大乘积。（和子数组最大累加和进行对比学习！！！）

图片说明

解题代码

class Solution {
public:
    double maxProduct(vector<double> arr) {
        double minVal = arr[0];
        double maxVal = minVal;
        double myres = minVal;
        for (int i = 1; i < arr.size(); i++) {
            double t_max = maxVal;
            //状态转移
            maxVal = max(max(arr[i], arr[i] * maxVal), minVal * arr[i]);//当前状态最大值
            minVal = min(min(arr[i], arr[i] * minVal), t_max * arr[i]);//当前状态最小值
            myres = max(myres, maxVal);//记录结果
        }
        return myres;
    }
};

复杂度分析
时间复杂度：循环一层，时间复杂度为 $O(N)$
空间复杂度：没有引入额外的地址空间，空间复杂度为 $O(1)$