思路：

由题目中给到的信息：

• 数组是double型，可正可负可零，也即是说乘积可能突然变小（正x负）也可能突然变大（负x负）
• 返回的子数组必须是连续的一段

这是一道典型的动态规划的题，解题最重要的便是找到状态方程。

方法一：动态规划 如果设置max[i]表示当前i及之前的乘积最大值，min[i]表示当前i及之前的乘积最小值，对于下一个arr[i+1]，新一轮的最大值要么是max[i] * arr[i+1]（max为正，arr为正），要么是min[i] * arr[i+1]（min为负，arr为负），要么是arr[i+1]（max为负，arr为正）。因此每轮需要从这三个数中找到最大值。而边界值就是，第0个元素，可以直接赋值给max[0]min[0]。 最后max数组中记录的是每次遇到的最大值，将其取最大即可。

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)， 借助了两个辅助数组

方法二：动态规划改进 上述方法时间已经达到最优，事实上是浪费了很多不必要空间，以下是在时间不变的基础上对空间的改进： 不管是max还是min的第i-1个元素，都是上一轮循环的最大值和最小值，于是可以用临时变量来存储，每次循环更新即可，不需要用额外空间。同时，设置一个临时变量存储当前所遇到的最大值，每次循环计算出的最大值与其比较即可。

class Solution {
public:
    double maxProduct(vector<double> arr) {
        if(arr.size() == 0)   //首先判断空数组的情况
                return 0;     
        double res = arr[0];
        double max = arr[0];  //初始时，最大最小都为第一个元素
        double min = arr[0];
        for(int i = 1; i < arr.size(); i++)
        {   //寻找max * arr[i] min * arr[i] arr[i] 三者中的最大值与最小值
            double temp1 = max * arr[i] > min * arr[i] ? max * arr[i] : min * arr[i];
            double temp2 = max * arr[i] < min * arr[i] ? max * arr[i] : min * arr[i];
            max = temp1 > arr[i] ? temp1 : arr[i];
            min = temp2 < arr[i] ? temp2 : arr[i];
            res = res > max ? res : max;   //最大值进入res
            }  
            return res;
    }
};

复杂度分析：

• 时间复杂度：O(n)，遍历一遍数组，一个for循环
• 空间复杂度：O(1)，除了几个临时变量外，没有额外的空间，单个的临时变量不算空间