【学会动态规划】乘积为正数的最长子数组长度（21）

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode）

题目非常好懂就是返回乘积是正数的最长子数组的长度。

2. 算法原理

1. 状态表示

还是分成两种状态表示，

f [ i ] 表示以 i 位置为结尾的所有子数组中乘积为正数的最长长度

g [ i ] 表示以 i 位置为结尾的所有子数组中乘积为负数的最长长度

2. 状态转移方程

我们先来分析一下 f [ i ] 的情况：

当 f [ i ] 只选择自己的时候，如果 nums[ i ] > 0 长度就是 1 否则就是 0。

当 f [ i ] 选择加上后面的值的时候，如果 nums[ i ] > 0，长度就是 f [ i - 1 ] + 1

如果 nums[ i ] < 0 ，那么这个时候的长度就是 g [ i - 1 ] == 0 ? 0 : g [ i - 1 ] + 1

所以 f [ 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 ] 的情况，

当 f [ i ] 只选择自己的时候，如果 nums[ i ] > 0 长度就是 0 否则就是 1。

当 f [ i ] 选择加上后面的值的时候，如果 nums[ i ] < 0，长度就是 f [ i - 1 ] + 1

如果 nums[ i ] > 0 ，那么这个时候的长度就是 g [ i - 1 ] == 0 ? 0 : g [ i - 1 ] + 1

所以 g [ 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. 初始化

我们分析一下就能得出，把前面的虚拟节点初始化成 0 即可（也就是不用管）

4. 填表顺序

从左往右，两个表同时填写。

5. 返回值

我们应该返回 f 表中的最大值。

3. 代码编写

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1);
        auto g = f;
        int ans = 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;
            }
            else if(nums[i - 1] < 0) {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1]  + 1;
            }
            ans = max(ans, f[i]);
        }
        return ans;
    }
};

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~