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

题目主要信息:

• 给定一个double型数组，数组元素可正可负可0
• 需要找到连续子数组每个元素相乘的最大值

具体思路:

因为数组元素有正有负有0，因此如果我们用$max[i]max[i]$表示当前下标$ii$及之前的子数组乘积最大值，$min[i]min[i]$表示当前下标$ii$及之前的子数组乘积最小值，那么对于数组下一个元素$arr[i+1]arr[i+1]$，新一轮的最大值要么是$max[i]\ast arr[i+1]max[i]\; *\; arr[i+1]$（$max[i]max[i]$为正，$arr[i+1]arr[i+1]$为正），要么是$min[i]\ast arr[i+1]min[i]\; *\; arr[i+1]$（$min[i]min[i]$为负，$arr[i+1]arr[i+1]$为负），要么就是$arr[i+1]arr[i+1]$（$max[i]max[i]$为负，$arr[i+1]arr[i+1]$为正）。因此每次都有三种情况，只要在遍历数组过程中将其都找出来，取最大值即可。这种方法也是动态规划常用的状态方程。

• step 1：优先判断空数组的情况，如果不为空，则再创建两个辅助数组记录上述每轮的max与min，初始化都从第一个数组元素开始。
• step 2：遍历数组，每次需要上述上个乘积之间的最大值与最小值，记录入数组。
• step 3：从max数组中找到整个数组最大的乘积部分，我们可以使用*max_element()函数。

查找过程可以参考如下图示：

代码实现:

class Solution {
public:
    double maxProduct(vector<double> arr) {
        if(arr.size() == 0)   //首先判断空数组的情况
            return 0;    
        vector<double> max(arr.size()); //两个数组分别存储每次的最大值与最小值
        vector<double> min(arr.size());
        max [0] = arr[0];//初始化为第一个数
        min [0] = arr[0];
        for(int i = 1; i < arr.size(); i++)
        {   //寻找max * arr[i] min * arr[i] arr[i] 三者中的最大值与最小值
            double temp;
            temp = arr[i] > max[i - 1] * arr[i] ? arr[i] : max[i - 1] * arr[i];
            max[i] = temp > min[i - 1] * arr[i] ? temp : min[i - 1] * arr[i];
            temp = arr[i] < max[i - 1] * arr[i] ? arr[i] : max[i - 1] * arr[i];
            min[i]= temp < min[i - 1] * arr[i] ? temp : min[i - 1] * arr[i];
        }
        return *max_element(max.begin(), max.end()); //返回值为max数组中记录的最大值
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，只遍历了一次数组
• 空间复杂度：$O(n)O(n)$，借助了两个长度为$nn$的辅助数组