LeetCode.152乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
链接：https://leetcode-cn.com/problems/maximum-product-subarray

1.暴力

时间复杂度是O(N^2)的，TLE。

2.DP(O(N))

对数组每个元素(a)出现后，对answer会产生四种可能的影响(answer为当前的最大值，可能会随数组的遍历而一直在更新)：

• 如果a是正数，且当前answer是正数，那么answer = answer * a；
• 如果a是正数，且当前answer是负数，那么answer = a；
• 如果a是负数，且当前answer是负数，那么answer = answer * a；
• 如果a是负数，且当前answer是正数，那么answer不变。

从这里可以看出，answer可能为正，可能为负，要让answer可以为负，我们必须维护元素a之前的最小乘积，所以思路就是，用两个变量cmax和cmin分别维护到(假设当前索引为k)k-1为止的最大乘积和最小乘积：

• nums[k]>=0, cmax = max(cmax*nums[k], nums[k]); answer = max(cmax,answer);
• nums[k]<0, 交换camx和cmin, cmin = min(cmin*nums[i], nums[i]);

代码：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans = INT_MIN;
        int cmax = 1, cmin = 1;  //到i-1为止的最大值与最小值

        int n = nums.size();
        for(int i = 0; i<n ;i++){
            if(nums[i] < 0) swap(cmax,cmin);  //负数的出现会使最大值变成最小值，最小值变成最大值
            cmax = max(cmax*nums[i],nums[i]);
            cmin = min(cmin*nums[i],nums[i]);
            ans = max(ans,cmax);
        }
        return ans;
    }
};