152. 乘积最大子数组
链接: 152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
1.状态表示*
定义两个状态表示：
f[i] 表⽰：以 i 结尾的所有⼦数组的最⼤乘积。
g[i] 表⽰：以 i 结尾的所有⼦数组的最⼩乘积。
2.状态转移方程
遍历每⼀个位置的时候，我们要同步更新两个 dp 数组的值。
对于 f[i] ，也就是「以 i 为结尾的所有⼦数组的最⼤乘积」，对于所有⼦数组，可以分为：
- 当nums[i]>0 时， f[i]=max(f[i-1]*nums[i],nums[i]);
- 当nums[i]<0时，f[i]=g[i-1]*nums[i];
对于g[i],也就是「以 i 为结尾的所有⼦数组的最小乘积」，可以分为:
- 当nums[i]>0 时， g[i]=g[i-1]*nums[i];
- 当nums[i]<0时，g[i]=min(f[i-1]*nums[i],nums[i]);
3. 初始化
对于这些初始化较为简单的题，没有添加辅助节点，直接进行初始化
f[0]=nums[0]>0?nums[0]:0; g[0]=nums[0]>0?0:nums[0];
4. 填表顺序
根据「状态转移⽅程」易得，填表顺序为「从左往右」，其两个表一起填写
5. 返回值
返回f[]表中的最大值
代码：
int maxProduct(vector<int>& nums) { int n=nums.size(); //f表示乘积最大子数组的乘积 //g表示乘积最小子数组的乘积 vector<int> f(n),g(n); int Max=nums[0]; f[0]=nums[0]>0?nums[0]:0; g[0]=nums[0]>0?0:nums[0]; for(int i=1;i<n;i++) { if(nums[i]>0) { f[i]=max(f[i-1]*nums[i],nums[i]); g[i]=g[i-1]*nums[i]; } if(nums[i]<0) { f[i]=g[i-1]*nums[i]; g[i]=min(f[i-1]*nums[i],nums[i]); } // cout<<f[i]<<" "<<g[i]<<endl; Max=max(Max,f[i]); } return Max; }
1567. 乘积为正数的最长子数组长度
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连数组。
请你返回乘积为正数的最长子数组长度。
示例 1：
输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。
示例 2：
输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。
示例 3：
输入：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
1.状态表示*
定义两个状态表示：
f[i] 表⽰：以 i 结尾的所有⼦数组的乘积为正数的最长子数组长度。
g[i] 表⽰：以 i 结尾的所有⼦数组的乘积为负数的最长子数组长度。
2.状态转移方程
遍历每⼀个位置的时候，我们要同步更新两个 dp 数组的值。
对于 f[i] ，也就是「以 i 结尾的所有⼦数组的乘积为正数的最长子数组长度」，对于所有⼦数组，可以分为：
- 当nums[i]>0 时， f[i]=f[i-1]+1;
- 当nums[i]<0时，f[i]=g[i-1]==0?0:g[i-1]+1;
对于g[i],也就是「以 i 为结尾的所有⼦数组的最小乘积」，可以分为:
- 当nums[i]>0 时， g[i]=g[i-1]==0?0:g[i-1]+1;
- 当nums[i]<0时，g[i]=f[i-1]+1;
3. 初始化
对于这些初始化较为简单的题，没有添加辅助节点，直接进行初始化
if(nums[0]>0) f[0]=1; else if(nums[0]<0) g[0]=1;
4. 填表顺序
根据「状态转移⽅程」易得，填表顺序为「从左往右」，其两个表一起填写
5. 返回值
返回f[]表中的最大值
代码：
int getMaxLen(vector<int>& nums) { int n=nums.size(); //以 i位置为最后一个位置时 //f[] 表示的正，g[]表示的是负 vector<int> f(n),g(n); if(n==1) { if(nums[0]>0) return 1; else return 0; } if(nums[0]>0) f[0]=1; else if(nums[0]<0) g[0]=1; int Max=0; for(int i=1;i<n;i++) { if(nums[i]>0) { f[i]=f[i-1]+1; g[i]=g[i-1]==0?0:g[i-1]+1; } if(nums[i]<0) { f[i]=g[i-1]==0?0:g[i-1]+1; g[i]=f[i-1]+1; } if(nums[i]==0) { f[i]=g[i]=0; } Max=max(Max,f[i]); } return Max; }
