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

题意思路：

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

方法一:暴力枚举

每次选取当前元素的所有子数组判断得到的最大值

复杂度分析

时间复杂度：O()，表示数组的长度。

空间复杂度：O()。除了几个临时变量外，没有额外的空间。

class Solution {
public:
    double maxProduct(vector<double> arr) {
       double ans=arr[0];
        for(int i=0;i<arr.size();i++){//循环每个元素
            double res=1;
            for(int j=i;j<arr.size();j++){//枚举以当前i元素为起点的子矩阵
                res*=arr[j];
                ans=max(ans,res);
            }
        }
        return ans;
    }
};

方法二：动态规划

求数组的所有子矩阵，因为乘积的结果由连续的数组得到，而且数组中会有0和负数，

两个负数相乘的结果也许大于最大值，所有我们也要记录当前子矩阵的最小值

通过从集合角度可以分析出状态转移方程：

可以使用滚动数组优化，每次都使用固定的几个存储空间，来达到压缩，节省存储空间的作用。起到优化空间，主要应用在递推或动态规划中。

因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。

图文详解：

复杂度分析

时间复杂度：O()，表示数组的长度。

空间复杂度：O()。除了几个临时变量外，没有额外的空间。

class Solution {
public:
    double maxProduct(vector<double> arr) {
       double mi=arr[0],mx=arr[0],ans=arr[0];
        for(int i=1;i<arr.size();i++){//滚动数组 不需要开数组记录
            double last_mx=mx;//会覆盖当前更新完fmax，所以需要特殊记录
            mx=max(max(arr[i],arr[i]*mx),arr[i]*mi);//状态转移方程
            mi=min(min(arr[i],arr[i]*last_mx),arr[i]*mi);
            ans=max(ans,mx);
        }
        return ans;
    }
};