动态规划：求乘积为正数的最长子数组长度

题目分析

给定一个整数数组，要求找到乘积为正数的最长连续子数组的长度。

核心思路

这道题是经典的动态规划问题。关键在于理解乘法的符号变化规律：正数乘正数为正，负数乘负数为正，而零会直接中断乘积序列。因此，在遍历数组时，我们需要同时维护两个状态：

1. 以当前位置结尾，乘积为正数的最长子数组长度。
2. 以当前位置结尾，乘积为负数的最长子数组长度。

为什么需要维护负数长度？因为如果当前数字是负数，它乘以之前的'负数乘积子数组'就会变成正数。如果我们只记录正数长度，遇到负数时就会丢失信息，无法判断后续能否翻盘。

状态定义与转移

设 f[i] 表示以第 i 个元素结尾的乘积为正数的最长子数组长度，g[i] 表示以第 i 个元素结尾的乘积为负数的最长子数组长度。

当遍历到 nums[i] 时：

• 如果 nums[i] > 0：
  • 正数延续正数：f[i] = f[i-1] + 1
  • 负数延续负数：g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1（如果之前没有负数序列，当前正数也无法形成负数序列）
• 如果 nums[i] < 0：
  • 负数延续正数变负数：g[i] = f[i-1] + 1
  • 正数延续负数变正数：f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1
• 如果 nums[i] == 0：
  • 正负序列长度都重置为 0，因为乘积变为 0，不再满足正数或负数条件。

注意处理边界情况，比如初始状态。为了简化代码逻辑，我们可以将下标整体右移一位，或者在循环中处理第一个元素。

代码实现

下面是基于 C++ 的动态规划解法，使用了滚动变量优化空间，但为了逻辑清晰，这里展示标准的 DP 表写法。

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        // f[i]: 以 i 结尾的正数乘积最长长度
        // g[i]: 以 i 结尾的负数乘积最长长度
        vector<int> f(n + 1, 0);
        vector<int> g(n + 1, 0);
        
        int ret = 0;
        
        for (int i = 1; i <= n; ++i) {
             (nums[i - ] > ) {
                f[i] = f[i - ] + ;
                g[i] = g[i - ] ==  ?  : g[i - ] + ;
            }   (nums[i - ] < ) {
                g[i] = f[i - ] + ;
                f[i] = g[i - ] ==  ?  : g[i - ] + ;
            }
            
            ret = (ret, f[i]);
        }
        
         ret;
    }
};