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