线性动态规划：乘积最大子数组的变种——乘积为正数的最长子数组长度 题目描述 给定一个整数数组 nums ，数组中的元素可能为正数、负数或零。要求找出乘积为正数的连续子数组的最大长度。注意，乘积为正数意味着子数组中负数的个数必须为偶数（且不能包含零，因为零会使乘积为零）。 解题过程 问题分析 乘积的正负性由负数的个数决定：偶数个负数相乘为正，奇数个负数相乘为负。 若子数组包含零，乘积为零，不符合要求。因此有效子数组不能跨越零（零将数组分割为多个段）。 思路：以零为分界，将数组划分为多个非零段，对每个段分别计算最长乘积正数的子数组长度，最后取最大值。 关键观察 在非零段中，若整个段乘积为正，则整个段长度是候选值。 若段乘积为负，则需要去掉一个负数（第一个或最后一个负数），使得剩余部分乘积为正。例如，段中负数位置为 neg[0], neg[1], ..., neg[k-1] ，则去掉 neg[0] 左边部分（包括 neg[0] ）或去掉 neg[k-1] 右边部分（包括 neg[k-1] ），剩余部分乘积为正。 动态规划状态定义 使用两个变量记录以当前元素结尾的乘积正数/负数的最长子数组长度： pos_len ：以 nums[i] 结尾的乘积为正数的最长子数组长度。 neg_len ：以 nums[i] 结尾的乘积为负数的最长子数组长度。 状态转移方程 遍历数组，根据当前值更新状态： 若 nums[i] > 0 ： 乘积正数长度可继承前一个正数长度并加1： pos_len = pos_len_prev + 1 。 若前一个负数长度不为零，乘积负数长度可继承并加1（正数不改变负号）： neg_len = neg_len_prev + 1 （若前一个负数长度为零，则当前无法形成负数乘积）。 若 nums[i] < 0 ： 乘积正数长度由前一个负数长度决定：若前一个负数长度非零，则 pos_len = neg_len_prev + 1 ；否则无法形成正数乘积（ pos_len = 0 ）。 乘积负数长度由前一个正数长度决定： neg_len = pos_len_prev + 1 （因为正数乘负数得负数）。 若 nums[i] == 0 ： 重置状态： pos_len = 0 , neg_len = 0 （因为子数组不能包含零）。 算法步骤 初始化 max_len = 0 , pos_len = 0 , neg_len = 0 。 遍历 i 从 0 到 n-1 ： 若 nums[i] > 0 ： pos_len = pos_len + 1 neg_len = neg_len > 0 ? neg_len + 1 : 0 （仅当之前有负数乘积时才更新） 若 nums[i] < 0 ： 临时保存 prev_pos = pos_len pos_len = neg_len > 0 ? neg_len + 1 : 0 neg_len = prev_pos + 1 若 nums[i] == 0 ： pos_len = 0 neg_len = 0 更新 max_len = max(max_len, pos_len) 。 返回 max_len 。 示例 数组 nums = [1, -2, 3, -4, 5] ： i=0: num=1>0 → pos_ len=1, neg_ len=0 → max_ len=1 i=1: num=-2<0 → prev_ pos=1 → pos_ len=0 (因neg_ len=0), neg_ len=2 → max_ len=1 i=2: num=3>0 → pos_ len=0+1=1, neg_ len=2+1=3 → max_ len=1 i=3: num=-4<0 → prev_ pos=1 → pos_ len=3+1=4, neg_ len=1+1=2 → max_ len=4 i=4: num=5>0 → pos_ len=4+1=5, neg_ len=2+1=3 → max_ len=5 结果：5（子数组为整个数组，乘积为正）。 总结 通过维护以每个位置结尾的乘积正/负的最长子数组长度，可在线性时间内解决问题。注意状态转移时根据当前值的正负性交换或扩展长度，遇到零时重置状态。