How do I handle zeroes in the array?

Zeroes divide the array into smaller subarrays. Any subarray containing zeroes cannot contribute to the product, so treat each segment between zeroes as an independent subarray.

What is the state transition dynamic programming pattern?

State transition dynamic programming helps track two states for each subarray: the length of the subarray with a positive product and the length with a negative product.

How does the negative number handling affect the product?

When two negative numbers are encountered, the product flips from negative to positive. This is why it's important to track negative product lengths and update them accordingly.

Can this problem be solved without dynamic programming?

It can be solved using a greedy approach by simply splitting the array by zeroes and calculating the subarray lengths manually, but dynamic programming makes it more efficient.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the array, as we iterate through the array once and use constant-time operations for each element.

#1567

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。请你返回乘积为正数的最长子数组长度。示例 1：输入： nums = [1,-2,-3,4] 输出： 4 解释：数组本身乘积就是正数，值为 24 。示例 2： …

数组动态规划贪心

题目描述

给你一个整数数组 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

lightbulb

解题思路

方法一：动态规划

我们定义两个长度为 $n$ 的数组 $f$ 和 $g$ ，其中 $f[i]$ 表示以 $\textit{nums}[i]$ 结尾的乘积为正数的最长子数组的长度，而 $g[i]$ 表示以 $\textit{nums}[i]$ 结尾的乘积为负数的最长子数组的长度。

初始时，如果 $\textit{nums}[0] > 0$ ，则 $f[0] = 1$ ，否则 $f[0] = 0$ ；如果 $\textit{nums}[0] < 0$ ，则 $g[0] = 1$ ，否则 $g[0] = 0$ 。我们初始化答案 $ans = f[0]$ 。

接下来，我们从 $i = 1$ 开始遍历数组 $\textit{nums}$ ，对于每个 $i$ ，我们有以下几种情况：

如果 $\textit{nums}[i] > 0$ ，那么 $f[i]$ 可以由 $f[i - 1]$ 转移而来，即 $f[i] = f[i - 1] + 1$ ，而 $g[i]$ 的值取决于 $g[i - 1]$ 是否为 $0$ ，如果 $g[i - 1] = 0$ ，则 $g[i] = 0$ ，否则 $g[i] = g[i - 1] + 1$ ；
如果 $\textit{nums}[i] < 0$ ，那么 $f[i]$ 的值取决于 $g[i - 1]$ 是否为 $0$ ，如果 $g[i - 1] = 0$ ，则 $f[i] = 0$ ，否则 $f[i] = g[i - 1] + 1$ ，而 $g[i]$ 可以由 $f[i - 1]$ 转移而来，即 $g[i] = f[i - 1] + 1$ 。
然后，我们更新答案 $ans = \max(ans, f[i])$ 。

遍历结束后，返回答案 $ans$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        f = [0] * n
        g = [0] * n
        f[0] = int(nums[0] > 0)
        g[0] = int(nums[0] < 0)
        ans = f[0]
        for i in range(1, n):
            if nums[i] > 0:
                f[i] = f[i - 1] + 1
                g[i] = 0 if g[i - 1] == 0 else g[i - 1] + 1
            elif nums[i] < 0:
                f[i] = 0 if g[i - 1] == 0 else g[i - 1] + 1
                g[i] = f[i - 1] + 1
            ans = max(ans, f[i])
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a solution that can split the array by zeroes and uses dynamic programming to keep track of the lengths of positive subarrays.
question_mark
Check if the candidate handles negative numbers and updates the product state accordingly.
question_mark
The candidate should be able to distinguish between the greedy approach for splitting the array and dynamic programming for tracking subarray lengths.

warning

常见陷阱

外企场景

error
Failing to handle zeroes correctly, treating them as part of subarrays.
error
Incorrectly updating the state for negative numbers, leading to wrong subarray length calculations.
error
Not splitting the array at zeroes, which results in incorrect handling of subarrays that contain zeroes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing the solution without using dynamic programming, focusing only on greedy subarray splitting.
arrow_right_alt
Modifying the approach to return the subarray itself, not just the length.
arrow_right_alt
Optimizing the space complexity to O(1) by avoiding extra storage for the state.

help

常见问题

外企场景

继续练习

#1578 使绳子变成彩色的最短时间 #1537 最大得分 #1526 形成目标数组的子数组最少增加次数