子数组最大乘积

描述: 给定一个double类型的数组arr，其中的元素可正可负可0，返回连续子数组累乘的最大乘积。

解法1：暴力求解

求子数组的最大乘积，最简单的方式是直接暴力遍历每一个子数组，求得最大的积即可。

Java实现如下：

public double maxProduct01(double[] arr) {
    double max = Double.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        double sum = 1;
        for (int j = i; j < arr.length; j++) {
            sum *= arr[j];
            // 求得子数组arr[i]~arr[j]的积，更新最大值
            max = Math.max(max, sum);
        }
    }
    return max;
}

C++实现如下：

class Solution {
public:
    double maxProduct(vector<double> arr) {
        double res = arr[0];
        for (int i = 0; i < arr.size(); i++) {
            double sum = 1;
            for (int j = i; j < arr.size(); j++) {
                sum *= arr[j];
                // 求得子数组arr[i]~arr[j]的积，更新最大值
                res = max(res, sum);
            }
        }
        return res;
    }
};

时间复杂度：O(N^2)

空间复杂度：O(1)

解法2：动态规划

本题要求最大子序积，是【最大子序和】的加强版，动态规划是最优解法。
在最大子序和中，状态转移方程为

f(i)=max{f(i−1)+arr[i], arr[i]}

f(i)是数组的局部最大子序和，求出最大的f(i)即可。

最大子序积中，需要考虑负数的问题，因为一个负数乘以一个负数可能会变为最大值。于是我们维护局部最大值fmax(i)和局部最小值fmin(i),状态转移方程如下：

fmax(i) = max{fmax(i-1)*arr[i], fmin(i-1)*arr[i], arr[i]}
fmin(i) = min{fmin(i-1)*arr[i], fmax(i-1)*arr[i], arr[i]}

Java实现如下：

public double maxProduct(double[] arr) {
    double min = arr[0];
    double max = min;
    double res = min;
    for (int i = 1; i < arr.length; i++) {
        double t_max = max;
        //局部最大值可以从哪些地方产生：1. arr[i]  2. min*arr[i]  3. max*arr[i]
        max = Math.max(Math.max(arr[i], arr[i] * max), min * arr[i]);
        //局部最小值可以从哪些地方产生：1. arr[i]  2. max*arr[i]  3. min*arr[i]
        min = Math.min(Math.min(arr[i], arr[i] * min), t_max * arr[i]);
        //更新全局最大值
        res = Math.max(res, max);
    }
    return res;
}

C++实现如下：

class Solution {
public:
    double maxProduct(vector<double> arr) {
        double minVal = arr[0];
        double maxVal = minVal;
        double res = minVal;
        for (int i = 1; i < arr.size(); i++) {
            double t_max = maxVal;
            //局部最大值可以从哪些地方产生：1. arr[i]  2. min*arr[i]  3. max*arr[i]
            maxVal = max(max(arr[i], arr[i] * maxVal), minVal * arr[i]);
            //局部最小值可以从哪些地方产生：1. arr[i]  2. max*arr[i]  3. min*arr[i]
            minVal = min(min(arr[i], arr[i] * minVal), t_max * arr[i]);
            //更新全局最大值
            res = max(res, maxVal);
        }
        return res;
    }
};

时间复杂度：O(N)

空间复杂度：O(1)