好的，我为你随机选择一个在“线性动态规划”领域，且与你提供的已讲题目列表不重复的经典题目。

最大子段和问题的变种：乘积最大子数组的另一种视角——求最大乘积子数组的长度（当乘积为正时）

题目描述

给你一个整数数组 nums，数组中的元素可以是正整数、负整数或零。请找出乘积结果为正数的最长子数组的长度。注意，是连续的子数组（subarray）。

示例 1：

输入：nums = [1, -2, 3, 4]
输出：2
解释：乘积为正的最长子数组是 [3, 4]，乘积为 12，长度为 2。另一个子数组 [1, -2] 的乘积为 -2，不为正。

示例 2：

输入：nums = [0, 1, -2, -3, -4]
输出：3
解释：乘积为正的最长子数组是 [-2, -3, -4]，乘积为 (-2) * (-3) * (-4) = 24，长度为 3。注意 0 会中断乘积为正的连续性。

示例 3：

输入：nums = [-1, 2]
输出：1
解释：乘积为正的最长子数组是 [2]，长度为 1。[-1, 2] 的乘积为 -2，不是正数。

示例 4：

输入：nums = [1, 2, 3, 5, -6, 4, 0, 10]
输出：4
解释：乘积为正的最长子数组是 [1, 2, 3, 5]，长度为 4。0 的出现使得连续性被重置。

题目解析

这个问题是“乘积最大子数组”的一个变种，但我们不关心乘积的值，只关心乘积为正数时，能维持多长的连续子数组。其核心挑战在于如何处理负数和零：

1. 零：是“重置信号”。一旦遇到 0，包含 0 的任何子数组乘积都为 0。因此，我们必须从 0 之后重新开始计算。
2. 负数：是“符号翻转器”。单个负数会使乘积符号变反，两个负数又会使乘积符号变正。因此，我们需要跟踪两种状态：以当前位置结尾的，乘积为正的子数组长度，和乘积为负的子数组长度。

状态定义：
我们定义两个动态规划数组：

• pos[i]：表示以第 i 个元素（nums[i]）结尾的，且乘积为正数的最长子数组的长度。
• neg[i]：表示以第 i 个元素（nums[i]）结尾的，且乘积为负数的最长子数组的长度。

我们的最终答案就是所有 pos[i] 中的最大值。

解题过程

我们将用一个具体的例子来逐步推导：nums = [1, -2, 3, 4]。

初始化：
创建 pos 和 neg 数组，长度与 nums 相同。初始时，因为第一个元素前面没有数，所以长度要么是 1，要么是 0。
初始化 max_len = 0 用于记录答案。

步骤 1：处理第一个元素 nums[0] = 1

• 它是一个正数。
• 以它结尾的乘积为正的子数组，只有它自己 [1]，所以 pos[0] = 1。
• 以它结尾的乘积为负的子数组，不存在，所以 neg[0] = 0。
  此时 max_len = max(max_len, pos[0]) = 1。

当前状态：
i=0: nums=1, pos=1, neg=0

步骤 2：处理第二个元素 nums[1] = -2
我们需要根据 nums[1] 的符号，以及前一个位置的状态 (pos[0], neg[0]) 来计算 (pos[1], neg[1])。

关键推导逻辑：

• 如果 nums[i] > 0（正数）：

  • 想要得到以 i 结尾的正乘积子数组，有两种可能：
    1. 从 i 自己开始：[nums[i]]，长度为 1。
    2. 接在之前某个正乘积子数组的后面：因为正 * 正 = 正。所以 pos[i] = pos[i-1] + 1。
       两者取较大值，但这里其实可以统一为 pos[i] = pos[i-1] + 1。因为如果 pos[i-1] 是 0，0+1=1 就是从自己开始。
  • 想要得到以 i 结尾的负乘积子数组：
    1. 必须接在之前某个负乘积子数组的后面：因为负 * 正 = 负。所以 neg[i] = neg[i-1] + 1（前提是 neg[i-1] > 0）。
    2. 如果 neg[i-1] = 0，意味着前面无法提供负数乘积，那么单个正数 nums[i] 无法构成负乘积数组，所以 neg[i] = 0。

• 如果 nums[i] < 0（负数）：

  • 想要得到以 i 结尾的正乘积子数组：
    必须接在之前某个负乘积子数组的后面：因为负 * 负 = 正。所以 pos[i] = neg[i-1] + 1（前提是 neg[i-1] > 0）。
    如果 neg[i-1] = 0，那么只能是自己吗？不行，一个负数的乘积是负的。所以 pos[i] = 0。
  • 想要得到以 i 结尾的负乘积子数组：
    1. 从 i 自己开始：[nums[i]]，长度为 1。
    2. 接在之前某个正乘积子数组的后面：因为正 * 负 = 负。所以 neg[i] = pos[i-1] + 1。

• 如果 nums[i] == 0（零）：

  • 包含 0 的乘积必为 0，既不正也不负。所以 pos[i] = 0, neg[i] = 0。

回到例子，nums[1] = -2（负数）：

• pos[1] (正乘积长度) = 接在负乘积子数组后。neg[0] = 0，所以无法构成正乘积。pos[1] = 0。
• neg[1] (负乘积长度) = 从自己开始 (长度1) 或 接在正乘积子数组后。pos[0] = 1，所以 neg[1] = pos[0] + 1 = 2。这个长度为2的数组是 [1, -2]，乘积为 -2。
  此时 max_len = max(1, 0) = 1。

当前状态：
i=0: nums=1, pos=1, neg=0
i=1: nums=-2, pos=0, neg=2

步骤 3：处理第三个元素 nums[2] = 3（正数）

• pos[2] = 接在正乘积子数组后。pos[1]=0，所以 0+1=1。这个长度为1的数组是 [3]，乘积为3。
• neg[2] = 接在负乘积子数组后。neg[1]=2，所以 2+1=3。这个长度为3的数组是 [1, -2, 3]，乘积为 -6。
  此时 max_len = max(1, 1) = 1。

当前状态：
i=0: nums=1, pos=1, neg=0
i=1: nums=-2, pos=0, neg=2
i=2: nums=3, pos=1, neg=3

步骤 4：处理第四个元素 nums[3] = 4（正数）

• pos[3] = 接在正乘积子数组后。pos[2]=1，所以 1+1=2。这个长度为2的数组是 [3, 4]，乘积为12。
• neg[3] = 接在负乘积子数组后。neg[2]=3，所以 3+1=4。这个长度为4的数组是 [1, -2, 3, 4]，乘积为 -24。
  此时 max_len = max(1, 2) = 2。

最终结果 max_len = 2。

算法总结与复杂度

1. 定义状态：

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

2. 状态转移方程（对于 i >= 1）：

   • 如果 nums[i] > 0：
     • positive[i] = positive[i-1] + 1
     • negative[i] = negative[i-1] + 1 (如果 negative[i-1] > 0，否则为 0)
   • 如果 nums[i] < 0：
     • positive[i] = negative[i-1] + 1 (如果 negative[i-1] > 0，否则为 0)
     • negative[i] = positive[i-1] + 1
   • 如果 nums[i] == 0：
     • positive[i] = 0
     • negative[i] = 0

3. 初始状态：

   • 如果 nums[0] > 0: positive[0] = 1, negative[0] = 0
   • 如果 nums[0] < 0: positive[0] = 0, negative[0] = 1
   • 如果 nums[0] == 0: positive[0] = 0, negative[0] = 0

4. 计算答案：

   • 在遍历过程中，不断用 positive[i] 更新全局最大值 ans。

5. 复杂度分析：

   • 时间复杂度：O(n)，其中 n 是数组长度，我们只遍历了一遍数组。
   • 空间复杂度：O(1)。实际上，我们在计算 positive[i] 和 negative[i] 时，只依赖于 i-1 时刻的值，因此可以用两个变量 pos 和 neg 代替两个数组，将空间优化到常数级别。