淄博网站的建设,编程培训机构名字,长春网站网站推广公司设计,公司网站海报怎么做题目链接 Leetcode.1567 乘积为正数的最长子数组长度 Rating #xff1a; 1710 题目描述
给你一个整数数组 nums#xff0c;请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度…题目链接 Leetcode.1567 乘积为正数的最长子数组长度 Rating 1710 题目描述
给你一个整数数组 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] 。 提示
1nums.length1051 nums.length 10^51nums.length105−109nums[i]109-10^9 nums[i] 10^9−109nums[i]109
分析
首先要想子数组的乘积为正数那么子数组里面一定不包含 0而且负数的个数为偶数。
我们用 positive记录 正数 的个数我们用negative记录 负数 的个数我们用neg_pos(初始为 -1)记录 第一个负数出现的位置
在遍历的过程中会遇到以下三种情况
nums[i] 0遇到正数 positive就1。nums[i] 0遇到负数 negative就1如果此时 neg_pos -1说明 nums[i]是目前遇到的第一个负数更新 neg_pos i。nums[i] 0遇到 0positve重置为 0negative重置为 0neg_pos重置为 -1。相当于 0把每一个合法的子数组都截开了。
在更新答案ans的时候
如果当前子数组中的负数个数是偶数个即 negative % 2 0ans max(ans , positive negative)即当前整个子数组乘积都是正数。如果当前子数组中的负数个数是奇数个即 negative % 2 ! 0那么当前子数组就需要剔除一个负数来保证整个子数组乘积为正数我们就选择剔除 第一个出现的负数。即 ans max(ans , i - neg_pos)剔除了 下标为neg_pos的负数。
时间复杂度O(n)O(n)O(n)
C代码
class Solution {
public:int getMaxLen(vectorint nums) {int positive 0,negative 0,neg_pos -1;int ans 0;int n nums.size();for(int i 0;i n;i){int x nums[i];if(x 0) positive;else if(x 0){negative;if(neg_pos -1) neg_pos i;}else{positive 0;negative 0;neg_pos -1;}if(negative % 2 0) ans max(ans,negative positive);else ans max(ans,i - neg_pos);}return ans;}
};Java代码
class Solution {public int getMaxLen(int[] nums) {int positive 0;int negative 0;int neg_pos -1;int n nums.length;int ans 0;for(int i 0;i n;i){int x nums[i];if(x 0) positive;else if(x 0){negative;if(neg_pos -1) neg_pos i;}else{positive 0;negative 0;neg_pos -1;}if(negative % 2 0) ans Math.max(ans,negative positive);else ans Math.max(ans,i - neg_pos);}return ans;}
}
