给你一个整数数组 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
方法一：动态规划
可以使用动态规划得到乘积为正数的最长子数组长度。定义两个数组 positive 和 negative，其中 positive}[i] 表示以下标 i 结尾的乘积为正数的最长子数组长度，negative}[i] 表示乘积为负数的最长子数组长度。
当 i=0 时，以下标 i 结尾的子数组的长度为 1，因此当 nums}[0]>0 时 positive}[0]=1，当 nums}[0]<0 时 negative}[0]=1。
当 i>1 时，根据 nums}[i] 的值计算 positive}[i] 和 negative}[i] 的值。
当 nums}[i]>0 时，之前的乘积乘以 nums}[i] 不会改变乘积的正负性。
positive}[i] 的计算为：
\textit{positive}[i]=\textit{positive}[i-1]+1
negative}[i] 的计算为：
\textit{negative}[i]=\begin{cases}
\textit{negative}[i-1]+1, & \textit{negative}[i-1]>0 \
0, & \textit{negative}[i-1] = 0
\end{cases}
这是因为当 negative}[i-1]=0 时，negative}[i] 本身无法形成一个乘积为正数的子数组，所以要特殊判断。
当 nums}[i]<0 时，之前的乘积乘以 nums}[i] 会改变乘积的正负性。
positive}[i] 的计算为：
\textit{positive}[i]=\begin{cases}
\textit{negative}[i-1]+1, & \textit{negative}[i-1]>0 \
0, & \textit{negative}[i-1] = 0
\end{cases}
这是因为当 negative}[i-1]=0 时，positive}[i] 本身无法形成一个乘积为负数的子数组，所以要特殊判断。
negative}[i] 的计算为：
\textit{negative}[i]=\textit{positive}[i-1]+1
当 nums}[i]=0 时，以下标 i 结尾的子数组的元素乘积一定为 0，因此有 positive}[i]=0 和 negative}[i]=0。
在计算 positive 和 negative 两个数组的过程中维护乘积为正数的最长子数组长度，当遍历结束时，即可得到最长子数组长度。
[sol11-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int getMaxLen(int[] nums) {
int length = nums.length;
int[] positive = new int[length];
int[] negative = new int[length];
if (nums[0] > 0) {
positive[0] = 1;
} else if (nums[0] < 0) {
negative[0] = 1;
}
int maxLength = positive[0];
for (int i = 1; i < length; i++) {
if (nums[i] > 0) {
positive[i] = positive[i - 1] + 1;
negative[i] = negative[i - 1] > 0 ? negative[i - 1] + 1 : 0;
} else if (nums[i] < 0) {
positive[i] = negative[i - 1] > 0 ? negative[i - 1] + 1 : 0;
negative[i] = positive[i - 1] + 1;
} else {
positive[i] = 0;
negative[i] = 0;
}
maxLength = Math.max(maxLength, positive[i]);
}
return maxLength;
}
}
|
[sol11-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
int getMaxLen(vector<int>& nums) {
int length = nums.size();
vector<int> positive(length), negative(length);
if (nums[0] > 0) {
positive[0] = 1;
}
else if (nums[0] < 0) {
negative[0] = 1;
}
int maxLength = positive[0];
for (int i = 1; i < length; ++i) {
if (nums[i] > 0) {
positive[i] = positive[i - 1] + 1;
negative[i] = (negative[i - 1] > 0 ? negative[i - 1] + 1 : 0);
}
else if (nums[i] < 0) {
positive[i] = (negative[i - 1] > 0 ? negative[i - 1] + 1 : 0);
negative[i] = positive[i - 1] + 1;
}
else {
positive[i] = 0;
negative[i] = 0;
}
maxLength = max(maxLength, positive[i]);
}
return maxLength;
}
};
|
[sol11-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution:
def getMaxLen(self, nums: List[int]) -> int:
length = len(nums)
positive, negative = [0] * length, [0] * length
if nums[0] > 0:
positive[0] = 1
elif nums[0] < 0:
negative[0] = 1
maxLength = positive[0]
for i in range(1, length):
if nums[i] > 0:
positive[i] = positive[i - 1] + 1
negative[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)
elif nums[i] < 0:
positive[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)
negative[i] = positive[i - 1] + 1
else:
positive[i] = negative[i] = 0
maxLength = max(maxLength, positive[i])
return maxLength
|
注意到 positive}[i] 和 negative}[i] 的值只与 positive}[i-1] 和 negative}[i-1] 有关，因此可以使用滚动数组优化空间。
[sol12-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int getMaxLen(int[] nums) {
int length = nums.length;
int positive = nums[0] > 0 ? 1 : 0;
int negative = nums[0] < 0 ? 1 : 0;
int maxLength = positive;
for (int i = 1; i < length; i++) {
if (nums[i] > 0) {
positive++;
negative = negative > 0 ? negative + 1 : 0;
} else if (nums[i] < 0) {
int newPositive = negative > 0 ? negative + 1 : 0;
int newNegative = positive + 1;
positive = newPositive;
negative = newNegative;
} else {
positive = 0;
negative = 0;
}
maxLength = Math.max(maxLength, positive);
}
return maxLength;
}
}
|
[sol12-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int getMaxLen(vector<int>& nums) {
int length = nums.size();
int positive = (nums[0] > 0);
int negative = (nums[0] < 0);
int maxLength = positive;
for (int i = 1; i < length; ++i) {
if (nums[i] > 0) {
++positive;
negative = (negative > 0 ? negative + 1 : 0);
}
else if (nums[i] < 0) {
int newPositive = negative > 0 ? negative + 1 : 0;
int newNegative = positive + 1;
tie(positive, negative) = {newPositive, newNegative};
}
else {
positive = negative = 0;
}
maxLength = max(maxLength, positive);
}
return maxLength;
}
};
|
[sol12-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def getMaxLen(self, nums: List[int]) -> int:
length = len(nums)
positive, negative = int(nums[0] > 0), int(nums[0] < 0)
maxLength = positive
for i in range(1, length):
if nums[i] > 0:
positive += 1
negative = (negative + 1 if negative > 0 else 0)
elif nums[i] < 0:
newPositive = (negative + 1 if negative > 0 else 0)
newNegative = positive + 1
positive, negative = newPositive, newNegative
else:
positive = negative = 0
maxLength = max(maxLength, positive)
return maxLength
|
复杂度分析
