受欢迎的赣州网站建设,网站建设咨询话术技巧,建设网站哪家专业,网页设计模板素材旅游1.题目解析 题目来源#xff1a;1567.乘积为正数的最长子数组——力扣 测试用例 2.算法原理 1.状态表示
因为数组中存在正数与负数#xff0c;如果求乘积为正数的最长子数组#xff0c;那么存在两种情况使得乘积为正数#xff0c;第一种就是正数乘以正数#xff0c;第… 1.题目解析 题目来源1567.乘积为正数的最长子数组——力扣 测试用例 2.算法原理 1.状态表示
因为数组中存在正数与负数如果求乘积为正数的最长子数组那么存在两种情况使得乘积为正数第一种就是正数乘以正数第二种就是负数乘以负数那么就必须使用两个表来分别存储这两种情况其中f表存储乘积为正数的子数组最长长度g表存储乘积为负数的子数组最长长度
f[i]:以第i个位置为结尾的乘积为正数的子数组最长长度
g[i]:以第i个位置为结尾的乘积为负数的子数组最长长度
2.状态转移方程
当遇到的为正数此时填两个表需要分别用到自己表的前一个位置的值也就是
f[i]f[i-1]1;g[i]g[i-1]0?0:g[i-1]1;这里特殊处理g表是因为当第i个位置之前乘积全为正数时g[i-1]0如果此时直接g[i]g[i-1]1则不符合实际情况
当遇到的为负数此时填两个表需要用到对方表内的前一个位置的值也就是
f[i]g[i-1]0?0:g[i-1]1;g[i]f[i-1]1;这里以及特殊处理g[i-1]避免错误
3.初始化
由于填表需要用到前一个位置的值所以可以开辟一个虚拟位置在循环内初始化两个表此时需要处理虚拟位置的值我们由状态转移方程可知在初始化第一个位置时用虚拟位置的值此时虚拟位置的值为0不会影响结果所以将虚拟位置置为0即可
4.填表顺序
从左到右两个表一起填写
5.返回值
返回f表的最大值即可 3.实战代码 class Solution {
public:int getMaxLen(vectorint nums) {int n nums.size();vectorint f(n1);vectorint g(n1);int ret INT_MIN;for(int i 1;i n;i){if(nums[i-1] 0){f[i] f[i-1] 1;g[i] g[i-1] 0 ? 0 : g[i-1] 1;}if(nums[i-1] 0){f[i] g[i-1] 0 ? 0 : g[i-1] 1;g[i] f[i-1] 1;}ret max(f[i],ret);} return ret;}
};
