难度: 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运行时间: 65 ms
内存: 29.6 MB
class Solution:
def getMaxLen(self, nums: List[int]) -> int:
nums.append(0)
n = len(nums)
stack = []
length = 0
pre = -1
ans =0
for i in range(n):
if nums[i] == 0:
if length:
last = i
k = len(stack)
if k % 2 == 0:
ans = max(ans, length)
else:
length -= min(stack[0] - pre, last - stack[-1])
ans = max(ans, length)
pre = i
stack = []
length = 0
else:
length += 1
if nums[i] < 0:
stack.append(i)
return ans
这个题解利用了一种遍历和记录策略，使用了栈来记录负数的索引位置。首先，代码在数组末尾添加了一个0作为哨兵值，以便处理到达数组末尾的情况。接着，通过遍历数组，记录每个非零元素的长度，同时记录遇到的负数的位置。当遇到0或者到达数组末尾时，根据栈中负数的数量决定如何计算最长的乘积为正的子数组长度。如果负数数量为偶数，整个区间乘积为正，直接更新最长长度。如果为奇数，则需要去掉一个负数，以确保子数组乘积为正，通常有两种去除方式：去掉最左边或最右边的负数，这取决于哪种方式能保留更长的子数组。最后，返回记录的最大长度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def getMaxLen(self, nums: List[int]) -> int:
nums.append(0) # 添加哨兵元素以简化边界处理
n = len(nums)
stack = [] # 用来存储负数的索引
length = 0 # 当前遍历的非零子数组的长度
pre = -1 # 上一个0的位置
ans = 0 # 结果变量，存储最长子数组的长度
for i in range(n):
if nums[i] == 0:
if length:
last = i
k = len(stack)
if k % 2 == 0:
ans = max(ans, length) # 如果负数个数为偶数，直接更新结果
else:
length -= min(stack[0] - pre, last - stack[-1]) # 去掉一个最不利的负数
ans = max(ans, length)
pre = i # 更新上一个0的位置
stack = [] # 清空栈
length = 0 # 重置当前长度
else:
length += 1 # 增加当前子数组的长度
if nums[i] < 0:
stack.append(i) # 记录负数的位置
return ans # 返回结果
在数组末尾添加一个0作为哨兵值可以简化边界处理。这样做确保了在数组的最后一个元素处理完毕后，可以统一处理以0为分隔符的逻辑，无论数组最后一个元素是否为0。这避免了在循环结束后还需要额外的逻辑来处理最后一个非零子数组的情况。简而言之，哨兵0可以作为一个自然的终止标记，让代码更简洁且易于理解。
在栈中记录负数索引的目的是为了在处理遇到的0时能够快速定位到当前非零子数组中所有负数的位置。这样做有助于快速计算当前子数组中负数的总数，并根据负数的奇偶性决定子数组的乘积正负。如果负数个数为偶数，则整个子数组的乘积为正；如果为奇数，则需要移除一个负数以确保乘积为正。通过栈来记录负数位置，可以有效地实现这一逻辑处理，特别是在需要计算移除某个负数后子数组长度的情况。
当栈中负数个数为奇数时，为了使子数组的乘积变为正，必须移除一个负数。选择去掉最左边或最右边的负数是为了最大化剩余子数组的长度。具体地，如果移除最左边的负数，则子数组从最左边负数的下一个位置开始到当前段的结束；如果移除最右边的负数，则子数组从当前段的开始到最右边负数的前一个位置结束。比较这两种方式后，选择可以保留更长子数组的方案。这种策略确保了在保持乘积为正的前提下，所得到的子数组尽可能长。
在数组中遇到连续的0时，每个0都会被视为一个新的分隔符，即它们各自独立地终止前一个非零子数组的计算，并重置后续非零子数组的起始点。因此，连续的0将导致多次重置子数组的长度和负数索引栈。这意味着每段非零子数组都是独立计算和评估的，连续的0之间不会有任何子数组长度的累加或传递。这种处理保证了算法的正确性和逻辑的清晰。