动态规划-子数组系列——1567.乘积为正数的最长子数组

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(vector<int>& nums) {int n = nums.size();vector<int> f(n+1);vector<int> g(n+1);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;}
};