难度中等
给你一个整数数组
nums
,请你求出乘积为正数的最长子数组的长度。一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例 1:
1 2 3
输入:nums = [1,-2,-3,4] 输出:4 解释:数组本身乘积就是正数,值为 24 。
示例 2:
1 2 3 4
输入:nums = [0,1,-2,-3,-4] 输出:3 解释:最长乘积为正数的子数组为 [1,-2,-3] ,乘积为 6 。 注意,我们不能把 0 也包括到子数组中,因为这样乘积为 0 ,不是正数。
示例 3:
1 2 3
输入:nums = [-1,-2,-3,0,1] 输出:2 解释:乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
示例 4:
1 2
输入:nums = [-1,2] 输出:1
示例 5:
1 2
输入:nums = [1,2,3,5,-6,4,0,10] 输出:4
提示:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
把数组想成1,0,-1三个数组成的,0是分隔数组的标志,
比如1 1 1 -1 0 1 1 1 0 1 1
,可以分成3块,1 1 1 -1
;1 1 1
;1 1
下面在每一块中套圈,规定圈中的-1的个数为偶数;
从第一个数开始套,遇到-1将flag取反,每前进一步length加1,将flag为正的length记录下来,遇到0重置。
有人可能会问为什么总是从第一个数开始套,万一第一个数字是负数-1 1 1 1
怎么办呢?用我的算法会计算成0,可是实际上是3,结果根本不对。
没事,咱们从后往前遍历一次就行了,-1 1 1 1
从后往前数,最大子数组长度不就是3了嘛。
这样能覆盖所有情况吗?
对于每块来说,只有偶数个-1 ,奇数个-1两种情况;偶数个-1自然是皆大欢喜,这一块全部算上;奇数个-1就得想一想了:
1 1 1 -1 1 1 1 1
一眼看出,-1把数组分成两半,左边数组最长为3,右边为4;如果从左边第一个开始遍历答案为3,从右边遍历最大为4,取两次遍历的最大值4即可。
1 1 1 1 1 -1 1 1 1 -2 1 1 -3 1 1 1
对于3 个负数来说的来说,最长的子数组会取-3左边所有数字,或者-1右边的所有数字,是不是从左向右遍历和从右向左遍历两遍就行了呢?
代码:
|
|