子数组最大乘积（贪心）

题意

一个有正负和零的double数组中，最大的子数组乘积为多少

思路分析

快速运算乘积

如果数组中没有零

计算数组一段的乘积，相当于计算从数组起始到结束的乘积，除以起始到数组开始之前的积

f(i,j) = premul[j] / premul[i-1]

局部最优

对于选中的结束位置j,我们要让f(i,j) 尽量大，则premul[i-1]的绝对值尽量小，且和它同号。

如果一正一负，取正值即可，不会发生运算。

零值

如果有零，零相当于把数组的分界线，只要乘积跨越了零始终是零，所以只用考虑被零值划分出的一个个小数组

状态维护

按符号不同分别维护，同符号的绝对值最小值

if(cur > 0){
    minpos = min(minpos, cur);
}else if(cur < 0){
    maxneg = maxneg == 1? cur : max(maxneg, cur);
}

记录答案

每次用 当前值 除以 和它同号的最小绝对值的值

ans = max(ans, cur/同号绝对值最小的)

题解

把上面的联系起来

class Solution {
public:
    double maxProduct(vector<double> arr) {
        if(arr.size() == 0)return 0;
        double ans = arr[0];
        double minpos = 1; // 最小正绝对值
        double maxneg = 1; // 最小负绝对值
        double cur = 1;
        for(auto v: arr){
            cur *= v;
            if(v == 0){ // 零值
                ans = max(ans,(double)0);
                cur = 1;
                minpos = maxneg = 1;
            }else if(cur > 0){ // 正
                ans = max(ans, cur / minpos);
                minpos = min(minpos, cur);
            }else if(cur < 0){ // 负
                ans = max(ans, cur / maxneg);
                maxneg = maxneg == 1? cur : max(maxneg, cur);
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度: 遍历数组操作，每个位置时间复杂度为常数，所以总时间复杂度为$O(n)O(n)$

空间复杂度: 只用了常数个额外变量，所以空间复杂度为$O(1)O(1)$