1.状态表示

因为数组中存在正数与负数如果求乘积为正数的最长子数组那么存在两种情况使得乘积为正数第一种就是正数乘以正数第二种就是负数乘以负数那么就必须使用两个表来分别存储这两种情况其中f表存储乘积为正数的子数组最长长度g表存储乘积为负数的子数组最长长度

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.填表顺序