乘积为正数的最长子数组长度 图解题解

乘积为正的最长子数组，到底在找什么

给一个整数数组 nums，有正有负、还可能有 0，找一段连续子数组（挨着的一截、不能跳挑），让这截乘起来为正，返回最长长度；乘积为 0 不算正。一段的正负只看负数个数，偶数个（含 0 个）为正，奇数个为负。nums=[1,-2,-3,4] 里 -2、-3 两负号成对抵消，整段为正，长度 4。

10⁵ 个数的 nums，把所有子数组都试一遍为什么跑不完

n 个数能划出约 n²/2 段连续子数组，逐段判正负再留最长，光枚举就 O(n²) 个（大 O 记号描述规模变大时操作数怎么涨），每段再乘一遍，叠成 O(n³)。浪费在相邻段符号重算。其实只要「以每个位置结尾乘积为正的最长段」，扫一遍递推（拿前一格推出后一格）就够。

为什么非得同时盯正、负两个长度

从左往右扫，要知道「以当前数结尾、乘积为正的最长段多长」。难点是负数翻转符号：正段碰负数变负，负段反而变正。只记正段不够，遇负数能翻出多长正段，来自之前攒的负段。所以同时维护两个状态（边扫边记、往后递推的量）：pos 记以当前位结尾乘积为正的最长长度，neg 记为负的。把 pos、neg 存下再往后推就是动态规划（DP）。

遇正数、负数、0，两个状态各怎么变

每读一个数按符号更新（这步叫转移，由前一格的 pos、neg 推出这一格）。遇 0：乘出来必不为正，pos、neg 清零，下段重起。遇正数：符号不变，pos=旧 pos+1；neg=旧 neg+1，但旧 neg 为 0 时仍是 0（没负段，正数乘不出负）。遇负数：正负互换，新 pos=旧 neg+1（旧 neg 为 0 则为 0，得先有负段可翻正），新 neg=旧 pos+1（接上正段成负段，没正段时自成长度 1 负段）。

负数这步必须同时取旧值——参考代码 pos, neg = (neg+1 if neg else 0), pos+1 一行赋值正为此。

拿 [1,-2,-3,4] 把两个状态逐格填出来

起点 pos=neg=ans=0。读 1（正）：pos=1、neg=0、ans=1。读 -2（负）：旧 neg 为 0 故新 pos=0，新 neg=旧 pos+1=2，ans 仍 1。读 -3（负）：新 pos=旧 neg+1=2+1=3（旧 neg=2 的负段被 -3 翻正），新 neg=旧 pos+1=0+1=1，ans=max(1,3)=3。读 4（正）：pos=旧 pos+1=4，neg=旧 neg+1=2，ans=max(3,4)=4。扫完 ans=4，正是整段 [1,-2,-3,4]。

负数分支先改 pos 再算 neg，答案为什么会莫名偏小

答案莫名偏小，多半栽在负数分支串用旧值：先写 pos=neg+1、再写 neg=pos+1，第二行的 pos 已是新值，neg 接错、后面每格跟着错。遇 0 忘清零，跨 0 的两段被拼成一条，长度虚高，可乘积明明是 0。凭空造出的假负段藏得深：遇正数旧 neg 为 0 还硬加 1、遇负数忘把新 pos 置 0，pos 都会接上不存在的负段、越算越大。复杂度：扫一趟、每数常数次判断，时间 O(n)；只用 pos、neg、ans 三个变量，空间 O(1)。

Python

from typing import List

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        pos = neg = ans = 0
        for x in nums:
            if x == 0:
                pos = neg = 0
            elif x > 0:
                pos += 1
                neg = neg + 1 if neg else 0
            else:
                pos, neg = (neg + 1 if neg else 0), pos + 1
            ans = max(ans, pos)
        return ans

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int pos = 0, neg = 0, ans = 0;
        for (int x : nums) {
            if (x == 0) pos = neg = 0;
            else if (x > 0) { ++pos; neg = neg ? neg + 1 : 0; }
            else { int oldPos = pos; pos = neg ? neg + 1 : 0; neg = oldPos + 1; }
            ans = max(ans, pos);
        }
        return ans;
    }
};

Java

import java.util.*;

class Solution {
    public int getMaxLen(int[] nums) {
        int pos = 0, neg = 0, ans = 0;
        for (int x : nums) {
            if (x == 0) { pos = 0; neg = 0; }
            else if (x > 0) { pos++; neg = neg == 0 ? 0 : neg + 1; }
            else { int oldPos = pos; pos = neg == 0 ? 0 : neg + 1; neg = oldPos + 1; }
            ans = Math.max(ans, pos);
        }
        return ans;
    }
}