动态规划

又是一个求连续区间数组的问题，典型的动态规划问题。
和求最大区间和不同的是，如果我们依然尝试用dp[i]表示以a[i]结尾的子区间的最大成绩。会发现由于负数的存在，会导致乘法结果反转。dp[i-1]a[i]反倒变成了最小值，无法得到状态转移方程。
沿着乘法的特性看，如果a[i]为负数，那么dpa[i]时，dp越大结果越小。dp越小结果越大。所以，我们只需要同时保存最大值和最小值，就可以写出状态转移方程了。
a[i] > 0时：
maxv[i] = max(a[i], a[i]*maxv[i-1])
minv[i] = min(a[i], a[i]*minv[i-1])
a[i] < 0时：
maxv[i] = max(a[i], a[i]*minv[i-1])
minv[i] = min(a[i], a[i]*maxv[i-1])
a[i]=0时，max和min肯定是0。
代码如下：

class Solution {
public:
    double maxProduct(vector<double> arr) {
        if(arr.empty()) return 0;
        vector<double> maxv(arr.si***v(arr.size());
        maxv[0] = minv[0] = arr[0];
        double maxsum = arr[0];
        for(int i = 1; i < arr.size(); i++) {
            double ai = arr[i];
            if(ai > 0) {
                maxv[i] = max(ai, maxv[i-1]*ai);
                minv[i] = min(ai, minv[i-1]*ai);
            } else {
                maxv[i] = max(ai, minv[i-1]*ai);
                minv[i] = min(ai, maxv[i-1]*ai);
            }
            maxsum = max(maxsum, maxv[i]);
        }
        return maxsum;
    }
};