152. 乘积最大子数组
题目描述:
给你一个整数数组nums,请你找出数组中乘积最大的非空连续子数组,并返回该子数组所对应的乘积
思路1:贪心
由于 n u m s [ i ] nums[i] 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
这题和最大子数组和的题型有一点像,但是不可以像它那样去进行转移,不能仅仅维护一个最大值,这样会忽略偶数个负数乘起来也是正数的情况,有一种局部贪心的感觉
所以还需要维护一个最小值
状态:
- m a x n [ i ] maxn[i] maxn[i]表示以 n u m s [ i ] nums[i] nums[i]结尾的子数组乘积的最大值
- m i n x [ i ] minx[i] minx[i]表示以 n u m s [ i ] nums[i] nums[i]结尾的子数组乘积的最小值
转移方程:
n u m [ i ] > 0 num[i] > 0 num[i]>0
- m a x n [ i ] = m a x ( n u m s [ i ] , m a x n [ i − 1 ] ∗ n u m s [ i ] ) ; maxn[i] = max(nums[i], maxn[i - 1] * nums[i]); maxn[i]=max(nums[i],maxn[i−1]∗nums[i]);
- m i n x [ i ] = m i n ( m i n x [ i − 1 ] ∗ n u m s [ i ] , n u m s [ i ] ) ; minx[i] = min(minx[i - 1] * nums[i], nums[i]); minx[i]=min(minx[i−1]∗nums[i],nums[i]);
n u m [ i ] < 0 num[i] < 0 num[i]<0
- m a x n [ i ] = m a x ( m i n x [ i − 1 ] ∗ n u m s [ i ] , n u m s [ i ] ) ; maxn[i] = max(minx[i - 1] * nums[i], nums[i]); maxn[i]=max(minx[i−1]∗nums[i],nums[i]);
- m i n x [ i ] = m i n ( m a x n [ i − 1 ] ∗ n u m s [ i ] , n u m s [ i ] ) ; minx[i] = min(maxn[i - 1] * nums[i], nums[i]); minx[i]=min(maxn[i−1]∗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;
}
};