leetcode 152. 乘积最大子数组「贪心」「动态规划」

152. 乘积最大子数组

题目描述：

给你一个整数数组nums，请你找出数组中乘积最大的非空连续子数组，并返回该子数组所对应的乘积

思路1：贪心

由于$nums[i]$都是整数，所以多乘一些数肯定不会让绝对值变小，所以我们就要尽可能多乘一些数

首先，我们考虑最简单的例子，也就是不包含0的情况：

• 统计负数的数量，如果是偶数，那直接返回所有数的乘积即可
• 如果负数的数量是奇数，我们就考虑删掉一个负数，由于我们上面说过，多乘一些数不会让乘积的绝对值变小，所以我们要尽可能少删数，从左往右找到第一个，下标为id1，从右往左找到第一个，下标为id2，要么是删id1往左的所有数，要么是删id2往右的所有数，两种情况取最大值就行
• 你可能会怀疑，为什么答案不可能是被删除的那一段，因为被删除的那一段都在另一半计算过了，删id1往左的所有数时，这段在计算删id2往右的所有数时，被计算过了

class Solution {
public:
    int fuck(int l, int r, vector<int>nums){
        if(l > r || l < 0 || r >= nums.size())return -2e9;
        if(l == r)return nums[l];
        int mul = 1;
        for(int i = l; i <= r; ++i)
            mul *= (nums[i] > 0 ? 1 : -1);
        if(mul > 0){
            for(int i = l; i <= r; ++i)mul *= nums[i];
            return mul;
        }
        mul = -1;
        int id1 = -1, id2 = -1;
        for(int i = l; i <= r; ++i){
            mul *= (nums[i] > 0 ? 1 : -1);
            if(mul > 0){
                id1 = i;
                break;
            }
        }
        int ans1 = 1, ans2 = 1;
        for(int i = id1 + 1; i <= r; ++i){
            ans1 *= nums[i];
        }
        mul = -1;
        for(int i = r; i >= l; --i){
            mul *= (nums[i] > 0 ? 1 : -1);
            if(mul > 0){
                id2 = i;
                break;
            }
        }
        for(int i = id2 - 1; i >= l; --i){
            ans2 *= nums[i];
        }
        return max(ans1, ans2);
    }
    int maxProduct(vector<int>& nums) {
        vector<int>v;
        for(int i = 0; i < nums.size(); ++i){
            if(nums[i] == 0)v.push_back(i);
        }
        if(v.empty())return fuck(0, nums.size() - 1, nums);
        int ans = 0;
        v.push_back(nums.size());
        int pre = -1;
        for(int i = 0; i < v.size(); ++i){
            ans = max(ans, fuck(pre + 1, v[i] - 1, nums));
            pre = v[i];
        }
        return ans;
    }
};

思路2:DP

这题和最大子数组和的题型有一点像，但是不可以像它那样去进行转移，不能仅仅维护一个最大值，这样会忽略偶数个负数乘起来也是正数的情况，有一种局部贪心的感觉

所以还需要维护一个最小值

• 状态：

  • $maxn[i]$表示以$nums[i]$结尾的子数组乘积的最大值
  • $minx[i]$表示以$nums[i]$结尾的子数组乘积的最小值

• 转移方程：

  • $num[i]>0$

    • $maxn[i]=max(nums[i],maxn[i-1]\ast nums[i]);$
    • $minx[i]=min(minx[i-1]\ast nums[i],nums[i]);$

  • $num[i]<0$

    • $maxn[i]=max(minx[i-1]\ast nums[i],nums[i]);$
    • $minx[i]=min(maxn[i-1]\ast nums[i],nums[i]);$

为了解决数据加强的问题，可以用double卡过去

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<double>maxn(n), minx(n);
        double ans = nums[0];
        maxn[0] = minx[0] = nums[0];
        for(int i = 1; i < n; ++i){
            if(nums[i] > 0){
                maxn[i] = max((double)nums[i], maxn[i - 1] * nums[i]);
                minx[i] = min(minx[i - 1] * nums[i], (double)nums[i]);
            }
            else if(nums[i] < 0){
                maxn[i] = max(minx[i - 1] * nums[i], (double)nums[i]);
                minx[i] = min(maxn[i - 1] * nums[i], (double)nums[i]);
            }
            ans = max(ans, maxn[i]);
        }
        return (int)ans;
    }
};