乘积为正数的最长子数组长度
字数 3218 2025-12-10 12:48:22

乘积为正数的最长子数组长度

题目描述
给定一个整数数组 nums，请你找出其所有连续子数组中，所有元素的乘积为正数的最长子数组的长度。注意，数组中的元素可能是正整数、负整数或零。

例如：
输入：nums = [1,-2,-3,4]
输出：4
解释：整个数组的乘积 1 * (-2) * (-3) * 4 = 24 为正数，所以最长子数组就是整个数组，长度为 4。

另一个例子：
输入：nums = [0,1,-2,-3,-4]
输出：3
解释：子数组 [-2,-3,-4] 的乘积为 (-2) * (-3) * (-4) = -24，是负数，不符合条件。而子数组 [1,-2,-3] 的乘积为 1 * (-2) * (-3) = 6 为正数，且长度 3 是最长的。实际上，子数组 [-2,-3,-4] 的乘积为负，不满足条件；子数组 [1,-2,-3] 长度为 3 且乘积为正，是最长的一个。

这个问题可以看作是对连续子数组乘积正负性的动态规划分析，我们需要高效地计算出每个位置结尾的最长乘积为正的子数组长度。

逐步解析
这个问题是最大子数组乘积（Maximum Product Subarray）的变体，但目标不是求最大乘积值，而是寻找乘积为正数的最长连续子数组长度。由于乘积的正负性取决于负数的个数以及是否遇到零，我们需要用状态来记录以每个位置结尾的子数组的正负乘积情况。

  1. 问题理解
    对于连续子数组，乘积的正负性规律如下：

    • 如果子数组中包含 0，乘积为 0，不满足“乘积为正”的条件。
    • 如果子数组中负数个数为偶数（包括 0 个负数），且没有 0，乘积为正。
    • 如果子数组中负数个数为奇数，且没有 0，乘积为负。

    所以，我们需要追踪以每个位置 i 结尾的子数组中，负数个数的奇偶性，并确保子数组中没有 0。

  2. 状态设计
    定义两个动态规划数组：

    • pos_len[i]：以 nums[i] 结尾的、乘积为正数的最长子数组长度。
    • neg_len[i]：以 nums[i] 结尾的、乘积为负数的最长子数组长度。

    这两个状态能帮助我们通过前一个位置的信息推导出当前位置的信息。注意，如果 nums[i] = 0，那么以它结尾的任何子数组乘积都是 0，所以 pos_len[i] = 0，neg_len[i] = 0，表示没有满足条件的子数组以 0 结尾。

  3. 状态转移
    考虑当前位置 i 的值 nums[i]：

    情况 1：nums[i] > 0

    • 乘积为正数的子数组：可以接在 i-1 的乘积为正的子数组后面（长度+1），或者自己单独作为一个子数组（长度 1，因为正数自身乘积为正）。
      所以 pos_len[i] = pos_len[i-1] + 1（如果 pos_len[i-1] > 0 则加 1，否则为 1，我们可以统一写作 pos_len[i] = (pos_len[i-1] > 0 ? pos_len[i-1] : 0) + 1，但实际上如果前一个位置有正乘积子数组，就接上；如果没有，就自己开始，但自己单独为正，所以至少是 1）。
      更精确地：pos_len[i] = pos_len[i-1] + 1，因为正数不会改变乘积的符号。
    • 乘积为负数的子数组：要得到负乘积，需要前面有一个乘积为负的子数组，然后接上这个正数，乘积符号不变，所以 neg_len[i] = (neg_len[i-1] > 0 ? neg_len[i-1] + 1 : 0)。如果前面没有乘积为负的子数组，那么以当前正数结尾不可能得到负乘积，所以为 0。

    情况 2：nums[i] < 0

    • 乘积为正数的子数组：要得到正乘积，需要前面有一个乘积为负的子数组，然后接上这个负数，负负得正。所以 pos_len[i] = (neg_len[i-1] > 0 ? neg_len[i-1] + 1 : 0)。如果前面没有乘积为负的子数组，那么以当前负数结尾要得到正乘积，只能前面有偶数个负数，但这里我们只依赖前一个状态，因为我们只关心以 i 结尾的情况，而状态 neg_len[i-1] 就记录了以 i-1 结尾的负乘积最长长度，接上当前负数正好变成正。另外，如果前面没有负乘积子数组，那么当前单独一个负数的乘积是负的，不能作为正乘积子数组，所以为 0。
    • 乘积为负数的子数组：可以接在前面乘积为正的子数组后面（正×负=负），或者自己单独作为一个负数子数组（长度 1，因为负数自身乘积为负）。所以 neg_len[i] = pos_len[i-1] + 1（因为正数乘积子数组接上这个负数变成负，如果前面没有正乘积子数组，那么当前负数单独长度为 1，也相当于 pos_len[i-1] = 0 时，neg_len[i] = 0 + 1 = 1，所以可以统一为 neg_len[i] = pos_len[i-1] + 1）。

    情况 3：nums[i] = 0
    以 0 结尾的任意子数组乘积都是 0，不可能是正或负，所以：
    pos_len[i] = 0，neg_len[i] = 0。

    另外，注意初始化：当 i=0 时，没有前一个位置，我们可以单独处理第一个元素，然后从 i=1 开始递推。也可以在代码中通过条件判断来处理。

  4. 边界条件与初始化
    对于 i=0：

    • 如果 nums[0] > 0：pos_len[0] = 1，neg_len[0] = 0。
    • 如果 nums[0] < 0：pos_len[0] = 0，neg_len[0] = 1。
    • 如果 nums[0] = 0：pos_len[0] = 0，neg_len[0] = 0。

  5. 最终答案
    在计算过程中，我们记录所有 pos_len[i] 的最大值，即所有位置结尾的乘积为正的最长子数组长度中的最大值。

  6. 例子推演
    以 nums = [1, -2, -3, 4] 为例：

    i=0, nums[0]=1>0: pos=1, neg=0
    i=1, nums[1]=-2<0:
    pos[1] = (neg[0]>0 ? neg[0]+1 : 0) = 0+0=0
    neg[1] = pos[0]+1 = 1+1=2
    解释：以 -2 结尾的乘积为正的子数组？前面没有乘积为负的子数组，所以不能由负负得正，单独 -2 是负，所以 pos=0。以 -2 结尾的乘积为负的子数组可以是 [1,-2]，长度 2。
    i=2, nums[2]=-3<0:
    pos[2] = neg[1]+1 = 2+1=3 （子数组 [1,-2,-3] 乘积为正）
    neg[2] = pos[1]+1 = 0+1=1 （子数组 [-3] 单独为负）
    i=3, nums[3]=4>0:
    pos[3] = pos[2]+1 = 3+1=4 （子数组 [1,-2,-3,4] 乘积为正）
    neg[3] = neg[2]+1 = 1+1=2 （子数组 [-3,4] 乘积为负）

    pos_len 数组为 [1,0,3,4]，最大值为 4，所以答案是 4。

  7. 复杂度分析

    • 时间复杂度：O(n)，只需要遍历数组一次。
    • 空间复杂度：O(n)，可以用两个一维数组存储状态，也可以优化为 O(1) 只保留前一个状态。

  8. 最终实现要点

    • 遍历数组，根据当前值的正负和前面的状态更新 pos_len 和 neg_len。
    • 遇到 0 时，两个状态都重置为 0。
    • 每次更新后，用 pos_len 更新全局最大值。

这个解法巧妙地用两个状态追踪了乘积的符号，从而避免了枚举所有子数组，高效解决了问题。

乘积为正数的最长子数组长度 题目描述 给定一个整数数组 nums ，请你找出其所有连续子数组中，所有元素的乘积为正数的最长子数组的长度。注意，数组中的元素可能是正整数、负整数或零。 例如： 输入：nums = [ 1,-2,-3,4 ] 输出：4 解释：整个数组的乘积 1 * (-2) * (-3) * 4 = 24 为正数，所以最长子数组就是整个数组，长度为 4。 另一个例子： 输入：nums = [ 0,1,-2,-3,-4 ] 输出：3 解释：子数组 [ -2,-3,-4] 的乘积为 (-2) * (-3) * (-4) = -24，是负数，不符合条件。而子数组 [ 1,-2,-3] 的乘积为 1 * (-2) * (-3) = 6 为正数，且长度 3 是最长的。实际上，子数组 [ -2,-3,-4] 的乘积为负，不满足条件；子数组 [ 1,-2,-3 ] 长度为 3 且乘积为正，是最长的一个。 这个问题可以看作是对连续子数组乘积正负性的动态规划分析，我们需要高效地计算出每个位置结尾的最长乘积为正的子数组长度。 逐步解析 这个问题是最大子数组乘积（Maximum Product Subarray）的变体，但目标不是求最大乘积值，而是寻找乘积为正数的最长连续子数组长度。由于乘积的正负性取决于负数的个数以及是否遇到零，我们需要用状态来记录以每个位置结尾的子数组的正负乘积情况。 问题理解 对于连续子数组，乘积的正负性规律如下： 如果子数组中包含 0，乘积为 0，不满足“乘积为正”的条件。 如果子数组中负数个数为偶数（包括 0 个负数），且没有 0，乘积为正。 如果子数组中负数个数为奇数，且没有 0，乘积为负。 所以，我们需要追踪以每个位置 i 结尾的子数组中，负数个数的奇偶性，并确保子数组中没有 0。 状态设计 定义两个动态规划数组： pos_len[i] ：以 nums[i] 结尾的、乘积为正数的最长子数组长度。 neg_len[i] ：以 nums[i] 结尾的、乘积为负数的最长子数组长度。 这两个状态能帮助我们通过前一个位置的信息推导出当前位置的信息。注意，如果 nums[i] = 0 ，那么以它结尾的任何子数组乘积都是 0，所以 pos_len[i] = 0 ， neg_len[i] = 0 ，表示没有满足条件的子数组以 0 结尾。 状态转移 考虑当前位置 i 的值 nums[i] ： 情况 1：nums[ i] > 0 乘积为正数的子数组：可以接在 i-1 的乘积为正的子数组后面（长度+1），或者自己单独作为一个子数组（长度 1，因为正数自身乘积为正）。 所以 pos_len[i] = pos_len[i-1] + 1 （如果 pos_len[i-1] > 0 则加 1，否则为 1，我们可以统一写作 pos_len[i] = (pos_len[i-1] > 0 ? pos_len[i-1] : 0) + 1 ，但实际上如果前一个位置有正乘积子数组，就接上；如果没有，就自己开始，但自己单独为正，所以至少是 1）。 更精确地： pos_len[i] = pos_len[i-1] + 1 ，因为正数不会改变乘积的符号。 乘积为负数的子数组：要得到负乘积，需要前面有一个乘积为负的子数组，然后接上这个正数，乘积符号不变，所以 neg_len[i] = (neg_len[i-1] > 0 ? neg_len[i-1] + 1 : 0) 。如果前面没有乘积为负的子数组，那么以当前正数结尾不可能得到负乘积，所以为 0。 情况 2：nums[ i] < 0 乘积为正数的子数组：要得到正乘积，需要前面有一个乘积为负的子数组，然后接上这个负数，负负得正。所以 pos_len[i] = (neg_len[i-1] > 0 ? neg_len[i-1] + 1 : 0) 。如果前面没有乘积为负的子数组，那么以当前负数结尾要得到正乘积，只能前面有偶数个负数，但这里我们只依赖前一个状态，因为我们只关心以 i 结尾的情况，而状态 neg_len[i-1] 就记录了以 i-1 结尾的负乘积最长长度，接上当前负数正好变成正。另外，如果前面没有负乘积子数组，那么当前单独一个负数的乘积是负的，不能作为正乘积子数组，所以为 0。 乘积为负数的子数组：可以接在前面乘积为正的子数组后面（正×负=负），或者自己单独作为一个负数子数组（长度 1，因为负数自身乘积为负）。所以 neg_len[i] = pos_len[i-1] + 1 （因为正数乘积子数组接上这个负数变成负，如果前面没有正乘积子数组，那么当前负数单独长度为 1，也相当于 pos_len[i-1] = 0 时， neg_len[i] = 0 + 1 = 1 ，所以可以统一为 neg_len[i] = pos_len[i-1] + 1 ）。 情况 3：nums[ i] = 0 以 0 结尾的任意子数组乘积都是 0，不可能是正或负，所以： pos_len[i] = 0 ， neg_len[i] = 0 。 另外，注意初始化：当 i=0 时，没有前一个位置，我们可以单独处理第一个元素，然后从 i=1 开始递推。也可以在代码中通过条件判断来处理。 边界条件与初始化 对于 i=0 ： 如果 nums[0] > 0 ： pos_len[0] = 1 ， neg_len[0] = 0 。 如果 nums[0] < 0 ： pos_len[0] = 0 ， neg_len[0] = 1 。 如果 nums[0] = 0 ： pos_len[0] = 0 ， neg_len[0] = 0 。 最终答案 在计算过程中，我们记录所有 pos_len[i] 的最大值，即所有位置结尾的乘积为正的最长子数组长度中的最大值。 例子推演 以 nums = [1, -2, -3, 4] 为例： i=0, nums[ 0 ]=1>0: pos=1, neg=0 i=1, nums[ 1]=-2 <0: pos[ 1] = (neg[ 0]>0 ? neg[ 0 ]+1 : 0) = 0+0=0 neg[ 1] = pos[ 0 ]+1 = 1+1=2 解释：以 -2 结尾的乘积为正的子数组？前面没有乘积为负的子数组，所以不能由负负得正，单独 -2 是负，所以 pos=0。以 -2 结尾的乘积为负的子数组可以是 [ 1,-2 ]，长度 2。 i=2, nums[ 2]=-3 <0: pos[ 2] = neg[ 1]+1 = 2+1=3 （子数组 [ 1,-2,-3 ] 乘积为正） neg[ 2] = pos[ 1]+1 = 0+1=1 （子数组 [ -3 ] 单独为负） i=3, nums[ 3 ]=4>0: pos[ 3] = pos[ 2]+1 = 3+1=4 （子数组 [ 1,-2,-3,4 ] 乘积为正） neg[ 3] = neg[ 2]+1 = 1+1=2 （子数组 [ -3,4 ] 乘积为负） pos_len 数组为 [ 1,0,3,4 ]，最大值为 4，所以答案是 4。 复杂度分析 时间复杂度：O(n)，只需要遍历数组一次。 空间复杂度：O(n)，可以用两个一维数组存储状态，也可以优化为 O(1) 只保留前一个状态。 最终实现要点 遍历数组，根据当前值的正负和前面的状态更新 pos_len 和 neg_len 。 遇到 0 时，两个状态都重置为 0。 每次更新后，用 pos_len 更新全局最大值。 这个解法巧妙地用两个状态追踪了乘积的符号，从而避免了枚举所有子数组，高效解决了问题。