152. Maximum Product Subarray.md

152. Maximum Product Subarray

思路

求最大连续子数组的积. 和之前的求最大连续子数组的和比较类似, 只是略微复杂一些, 因为遇到0会使整个乘积为0，而遇到负数，则会使最大乘积变成最小乘积.

思路一

采用动态规划的方法, 由于前面提到若遇到负数, 那么最小乘积会变成最大乘积, 所以我们不仅要记录最大乘积还要记录最小乘积.

我们开辟两个数组dp1和dp2, dp1[i]表示以nums[i]结尾的连续子数组的积的最大值, dp2[i]表示以nums[i]结尾的连续子数组的积的最小值. 那么不管nums[i]是正是负或者是0, 数组的更新方式均为:

• dp1[i] = max(nums[i], dp1[i-1]*nums[i], dp2[i-1]*nums[i]);
• dp2[i] = min(nums[i], dp1[i-1]*nums[i], dp2[i-1]*nums[i]);

我们在更新两个数组的过程中用res记录最大的乘积(res = max(res, dp1[i])), 最后返回res即可.

时空复杂度均为O(n).

思路一改进版

仔细分析思路一的过程我们可以发现每次计算dp1[i]时只用到了dp1[i-1]和dp2[i-1], 那么我们其实没必要开辟数组, 直接用变量dp1和dp2就行了. 这样空间复杂度就减小为O(1).

这是常规减小动归空间复杂度的思路.

C++

思路一

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int>dp1(nums.size(), 0);
        vector<int>dp2(nums.size(), 0);
        dp1[0] = nums[0]; dp2[0] = nums[0];
        int res = nums[0];
        for(int i = 1; i < nums.size(); i++){
            dp1[i] = max(dp1[i-1]*nums[i], max(dp2[i-1]*nums[i], nums[i]));
            dp2[i] = min(dp1[i-1]*nums[i], min(dp2[i-1]*nums[i], nums[i]));
            res = max(res, dp1[i]);
        }
        return res;
    }
};

思路一改进版

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int dp1 = nums[0], dp2 = nums[0], tmp1, tmp2;
        int res = nums[0];
        for(int i = 1; i < nums.size(); i++){
            tmp1 = dp1*nums[i]; tmp2 = dp2*nums[i];
            dp1 = max(tmp1, max(tmp2, nums[i]));
            dp2 = min(tmp1, min(tmp2, nums[i]));
            res = max(res, dp1);
        }
        return res;
    }
};