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;}
};