题目描述

给定一个整数数组 nums，请你求出乘积为正数的最长子数组的长度。

一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

请你返回乘积为正数的最长子数组长度。

样例

输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24。

输入：nums = [0,1,-2,-3,-4]
输出：3
解释：最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。

输入：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3]。

输入：nums = [-1,2]
输出：1

输入：nums = [1,2,3,5,-6,4,0,10]
输出：4

限制

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

算法

(遍历) $O(n)$

1. 对于每个位置，记录距离上一次遇到 0 时
   • 遇到负数的个数为偶数，则积为正数的最长长度为距离上一次 0 的位置。
   • 遇到负数的个数为奇数，则积为正数的最长长度为在上一次的 0 后，距离第一个负数位置。

时间复杂度

• 遍历数组一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

Go 代码

func getMaxLen(nums []int) int {
    const UNDEFINED = -1

    firstNegative := UNDEFINED
    lastZero := -1
    isNegative := false

    ans := 0
    for i, v := range nums {
        if v == 0 {
            lastZero = i
            isNegative = false
            lastNegative = UNDEFINED
        } else if v < 0 {
            isNegative = !isNegative
            if lastNegative == UNDEFINED {
                lastNegative = i
            }
        }

        if isNegative {
            ans = max(ans, i - lastNegative)
        } else {
            ans = max(ans, i - lastZero)
        }
    }

    return ans
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}