力扣题解（乘积最大子数组）
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
子数组
（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
本题思路是分两个数组分别保存前i个为正的最大值和前i个为负的最大值，然后对第i个为正，负分情况讨论。当第i个为正时，则pos[i]=pos[i-1]*num[i],negpos[i-1]=negpos[i]*num[i].当第i个为负时，则pos[i]=negpos[i-1]*num[i],negpos[i-1]=pos[i]*num[i].为0则全化为0即可。这类题的特点是存在频繁的正负号的转换，因此需要分别对正，负数保存。
ps：本题最后一个案例过不了，官方做法也是最后一个案例过不了，貌似是乘积过大导致。
class Solution {
public:
int maxProduct(vector<int>& nums) {
size_t n=nums.size();
vector<int>maxx(n,INT_MIN);//包含i的最大值
vector<int>minx(n,INT_MAX);
maxx[0]=minx[0]=nums[0];
for(int i=1;i<n;i++)
{
int cur=nums[i];
if(cur>=0)
{
maxx[i]=max(nums[i],maxx[i-1]*cur);
minx[i]=min(nums[i],minx[i-1]*cur);
}
else
{
maxx[i]=max(nums[i],minx[i-1]*cur);
minx[i]=min(nums[i],maxx[i-1]*cur);
}
}
int ret=nums[0];
for(int i=1;i<n;i++)
{
if(maxx[i]>ret)
{
ret=maxx[i];
}
}
return ret;
}
};
原文地址：https://blog.csdn.net/yyssas/article/details/140328087
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！