152-乘积最大子数组

LeetCode 152. Maximum Product Subarray

LeetCode-152

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

method

容易根据53-最大子数组和想到递推公式可能是

dp[i] = max(dp[i-1] * nums[i], nums[i]);

但这样不对，反例[5,6,-3,4,-3]对应的dp数组为[5,30,-3,4,-3]，这样得出的结果为30，但正确的结果是5*6*(-3)*4*(-3)，说明当前位置的最优解不一定是由前一个最优解转移得到的，所以分类讨论

• 如果nums[i]是正数，我们希望dp[i-1]也是正数，并且尽可能大，这样乘起来的结果更好
• 如果nums[i]是负数，我们希望dp[i-1]也是负数，并且尽可能小，这样乘起来结果也更好

所以维护两个dp数组分别记录以i结尾的子数组的累乘的最大值和最小值，递推公式还是dp[i]=max(dp[i-1] * nums[i], nums[i])，只不过多了一个dp数组，就要分开

int maxProduct(vector<int>& nums) {
    int n = nums.size();
    vector<int> dpMax(n);
    vector<int> dpMin(n);
    dpMax[0] = nums[0];
    dpMin[0] = nums[0];
    int res = nums[0];
    for (int i = 1; i < n; i++) {
        dpMax[i] = max({dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i], nums[i]});
        dpMin[i] = min({dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i], nums[i]});
        res = max(res, dpMax[i]);
    }
    return res;
}

因为只跟前一个结果有关，所以可以用滚动数组，因为dpMax可能会被更新，所以先记录下来

int maxProduct(vector<int>& nums) {
    int dpMax = nums[0];
    int dpMin = nums[0];
    int res = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        int tmp = dpMax;
        dpMax = max({dpMax * nums[i], dpMin * nums[i], nums[i]});
        dpMin = min({tmp * nums[i], dpMin * nums[i], nums[i]});
        res = max(res, dpMax);
    }
    return res;
}