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

这篇具有很好参考价值的文章主要介绍了【学会动态规划】乘积为正数的最长子数组长度（21）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

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

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

1. 题目解析

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

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

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

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