Medium

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

解题思路

这道题的关键在于理解什么情况下乘积为正数：

  1. 包含偶数个负数的子数组乘积为正
  2. 子数组中不能包含0，因为包含0会使乘积为0

核心思想： 我们可以将数组按照0分割成多个子段，然后对每个子段分别处理。对于每个不包含0的子段：

  • 如果负数个数为偶数，整个子段都可以取
  • 如果负数个数为奇数，我们需要去掉一个负数来使剩余部分的负数个数变为偶数

动态规划解法： 维护两个状态：

  • pos：以当前元素结尾的乘积为正数的最长子数组长度
  • neg：以当前元素结尾的乘积为负数的最长子数组长度

状态转移：

  • 如果当前元素为正数：pos = pos + 1, neg = neg > 0 ? neg + 1 : 0
  • 如果当前元素为负数：交换pos和neg，然后更新
  • 如果当前元素为0：重置pos和neg为0

这种方法时间复杂度为O(n)，空间复杂度为O(1)，是最优解。

代码实现

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

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

public class Solution {
    public int GetMaxLen(int[] nums) {
        int pos = 0, neg = 0, maxLen = 0;
        
        foreach (int num in nums) {
            if (num == 0) {
                pos = neg = 0;
            } else if (num > 0) {
                pos++;
                neg = neg > 0 ? neg + 1 : 0;
            } else { // num < 0
                int temp = pos;
                pos = neg > 0 ? neg + 1 : 0;
                neg = temp + 1;
            }
            maxLen = Math.Max(maxLen, pos);
        }
        
        return maxLen;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var getMaxLen = function(nums) {
    let maxLen = 0;
    let positiveLen = 0;
    let negativeLen = 0;
    
    for (let num of nums) {
        if (num === 0) {
            positiveLen = 0;
            negativeLen = 0;
        } else if (num > 0) {
            positiveLen++;
            negativeLen = negativeLen === 0 ? 0 : negativeLen + 1;
        } else {
            let temp = positiveLen;
            positiveLen = negativeLen === 0 ? 0 : negativeLen + 1;
            negativeLen = temp + 1;
        }
        maxLen = Math.max(maxLen, positiveLen);
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组一次
空间复杂度O(1)只使用了常数个变量