C++，动态规划，同时保存最大值和最小值，空间优化

    if(arr.empty()) return 0;
    vector<double> maxv(arr.size()),minv(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;

发现只与前一个状态有关，可进行空间优化

        double maxF = arr[0], minF = arr[0], ans = arr[0];
        for (int i = 1; i < arr.size(); ++i) {
            double mx = maxF, mn = minF;
            maxF = max(mx * arr[i], max(arr[i], mn * arr[i]));
            minF = min(mn * arr[i], min(arr[i], mx * arr[i]));
            ans = max(maxF, ans);
        }
        return ans;