题目

给定一个数组, 求连续子数组的最大乘积.

Input: [2,3,-2,4]
Output: 6
Input: [-2,0,-1]
Output: 0

思路1

循环
时间复杂度O(n)²

int maxProduct(vector<int>& nums) {
    if (nums.empty()) return 0;
    int res = nums[0];
    for (int i = 0; i < nums.size(); i++) {
        int temp = nums[i];
        res = max(res, temp);
        for (int j = i+1;j < nums.size();j++) {
            temp *= nums[j];
            if (temp > res) {
                res = temp;
            }
        }
        res = max(res, temp);
    }
    return res;
}

思路2

DP. 记录出前i个数的最大乘积和最小乘积,当第i个数为负可能就需要使用最小乘积.
时间复杂度O(n)

int maxProduct3(vector<int>& nums) {
    if (nums.empty()) return 0;
    int n = (int)nums.size();

    vector<int> maxP(n, 0), minP(n, 0);
    maxP[0] = nums[0];
    minP[0] = nums[0];
    int maxProduct = nums[0];

    for(int i = 1; i < n; i++){
        maxP[i] = max(nums[i], max(maxP[i-1] * nums[i], minP[i-1] * nums[i]));
        minP[i] = min(nums[i], min(minP[i-1] * nums[i], maxP[i-1] * nums[i]));
        maxProduct = max(maxProduct, maxP[i]);
    }

    return maxProduct;
 }