AlgoPressAppearance
1567-乘积为正数的最长子数组长度
https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product
给你一个整数数组 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] 。
示例 4：
输入：nums = [-1,2]
输出：1
示例 5：
输入：nums = [1,2,3,5,-6,4,0,10]
输出：4
提示： $$ 1 <= nums.length <= 10^5 -10^9 <= nums[i]<= 10^9 $$
解题思路【参考了0152方法2】
在一个非0数组中，
- 如果负数个数是偶数个，那么当前数组长度就是乘积为正数的最大子数组长度
- 如果负数个数是奇数个，那么从左往右相乘，如果最大值 如果遇到0，则重新计算
- 注意1 : [1000000,1000001] 如果直接用乘积
result*=nums[i]，可能结果会越界 - 注意2 : [0,1,-2,-3,-4] 0数字的处理
- 注意3 : Console.WriteLine debug的时候会超时，真正运行的时候可以注释掉该语句
csharp
public class Solution {
public int GetMaxLen(int[] nums) {
int result = 1;
int curLen = 0;
int maxLen = 0;
//从左往右
for(int i=0; i < nums.Length; i++){
if(nums[i] == 0){
result = 1;
curLen = 0;
}
else{
result *= nums[i] > 0 ? 1 : -1;
curLen++;
//Console.WriteLine("left to right {0}",curLen);
if(result > 0){
maxLen = Math.Max(curLen,maxLen);
}
}
}
//从右往左
result = 1;
curLen = 0;
for(int i=nums.Length - 1; i>=0; i--){
if(nums[i] == 0){
result = 1;
curLen = 0;
}
else{
result *= nums[i] > 0 ? 1 : -1;
curLen++;
//Console.WriteLine("right to left: result: {0}, len: {1}",result, curLen);
if(result >0){
maxLen = Math.Max(curLen,maxLen);
}
}
}
return maxLen;
}
}
解题思路2 ： 分别计算正数和负数的个数
注意：需要仔细考虑 nums[i] 为正数 和 为负数的符号变化，很容易混淆
csharp
public class Solution{
public int GetMaxLen(int[] nums){
int positive = nums[0] > 0 ? 1 : 0;
int negative = nums[0] < 0 ? 1 : 0;
int max = positive;
for(int i=1; i<nums.Length; i++){
if(nums[i] > 0){
//接下的数是 正数，直接加1就完事
positive++;
//负数×正数=负数 所以1.只要negetive存在 长度就加一 2.不存在 只有一个正数 负数在i位置长度为0
negative = negative == 0 ? 0 : negative+1;
}
else if(nums[i] < 0){
//nums<0 negative>0 负数×负数 变号->正连续 因为要求正连续 所以把这个值给positive，如果前面没有负数，那么就为0
int newPositive = negative > 0 ? negative + 1 : 0;
//nums<0 正数×负数 变号->负连续 不管正数是多少 ，往后加1
int newNegative = positive + 1;
positive = newPositive;
negative = newNegative;
}
else{
//因为nums=0直接砍断了连续，长度直接变成0
positive = 0;
negative = 0;
}
max = Math.Max(max,positive);
}
return max;
}
}
复习：20220701
注意符号转换， positive 表示当前正数的最大长度 negative 表示当前负数的最大长度， 注意这里计算长度的时候，如果刚刚是负数是按照 positive + 1, 在前面的负数是不算的 比如 -1, 2,3,4,-5,-6 到-5的时候，他的长度是 4 ，因为等第三次在遇到负数的时候，他的整数总长度是(negative+1)=6，第一个-1是不算的。
csharp
public class Solution {
public int GetMaxLen(int[] nums) {
int positive = nums[0] > 0 ? 1 : 0;
int negative = nums[0] < 0 ? 1 : 0;
int max = positive;
for(int i=1; i<nums.Length; i++){
if(nums[i] > 0){
positive = positive + 1;
negative = negative == 0 ? 0 : negative + 1;
}
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;
}
max = Math.Max(max,positive);
}
return max;
}
}