NC306. 乘积为正数的最长连续子数组
描述
给定一个长度为 n 的整数数组，请你找出其中最长的乘积为正数的子数组长度。
子数组的定义是原数组中一定长度的连续数字组成的数组。
数据范围： 
, 数组中的元素满足 
示例1
输入:
[1,2,3,-1,4]
输出:
3
示例2
输入:
[1,2,3,0,4]
输出:
3
NC306. 乘积为正数的最长连续子数组
描述
示例1
输入:
[1,2,3,-1,4]
输出:
3
示例2
输入:
[1,2,3,0,4]
输出:
3
C++ 解法, 执行用时: 35ms, 内存消耗: 4336KB, 提交时间: 2022-06-04
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int findLongestSubArray(vector<int>& nums) {
int i,sz=nums.size(),res=0;
if(sz)
{
vector<int> dp(sz,0);
if(nums[0]>0)
dp[0]=1;
res=dp[0];
for(i=1;i<sz;i++)
{
if(nums[i]>0)
dp[i]=dp[i-1]+1;
else if(nums[i]<0)
{
if((dp[i-1]<=i-1)&&(nums[i-1-dp[i-1]]<0))
{
dp[i]=dp[i-1]+2;
if((dp[i-1]<=i-2)&&(dp[i-2-dp[i-1]]>0))
dp[i]+=dp[i-2-dp[i-1]];
}
}
res=(res>=dp[i])?res:dp[i];
}
}
return res;
}
};
C++ 解法, 执行用时: 35ms, 内存消耗: 4356KB, 提交时间: 2022-08-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int findLongestSubArray(vector<int>& nums) {
// write code here
int i,sz=nums.size(),res=0;
if(sz)
{
vector<int> dp(sz,0);
if(nums[0]>0)
dp[0]=1;
res=dp[0];
for(i=1;i<sz;i++)
{
if(nums[i]>0)
dp[i]=dp[i-1]+1;
else if(nums[i]<0)
{
if((dp[i-1]<=i-1)&&(nums[i-1-dp[i-1]]<0))
{
dp[i]=dp[i-1]+2;
if((dp[i-1]<=i-2)&&(dp[i-2-dp[i-1]]>0))
dp[i]+=dp[i-2-dp[i-1]];
}
}
res=(res>=dp[i])?res:dp[i];
}
}
return res;
}
};
C++ 解法, 执行用时: 36ms, 内存消耗: 4252KB, 提交时间: 2022-05-04
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int findLongestSubArray(vector<int>& nums) {
// write code here
int n = nums.size();
if (n == 1) {
return nums[0] > 0 ? 1 : 0;
}
int ans = 0;
vector<int> dp(n);
dp[0] = nums[0] > 0 ? 1 : 0;
for (int i = 1; i < n; i++) {
if (nums[i] > 0) {
dp[i] = dp[i - 1] + 1;
} else if (nums[i] < 0) {
if (nums[i - 1 - dp[i - 1]] < 0 && i - 1 - dp[i - 1] >= 0) {
dp[i] = dp[i - 1] + 2;
if (i - 2 - dp[i - 1] >= 0 && dp[i - 2 - dp[i - 1]] > 0) {
dp[i] += dp[i - 2 - dp[i - 1]];
}
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};
C++ 解法, 执行用时: 36ms, 内存消耗: 4356KB, 提交时间: 2022-05-18
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int findLongestSubArray(vector<int>& nums) {
// write code here
int len=nums.size();
if(len==0) return 0;
vector<int> pos(len,0);
vector<int> neg(len,0);
pos[0]=nums[0]>0?1:0;
neg[0]=nums[0]<0?1:0;
int res=nums[0]>0?1:0;
for(int i=1;i<len;i++)
{
if(nums[i]==0)
{
pos[i]=0;
neg[i]=0;
}
else if(nums[i]>0)
{
pos[i]=1+pos[i-1];
neg[i]=(neg[i-1]>0?neg[i-1]+1:0);
}
else
{
// int temp=pos[i]
pos[i]=(neg[i-1]>0?neg[i-1]+1:0);
neg[i]=1+pos[i-1];
}
res=max(res,pos[i]);
}
return res;
}
};
C++ 解法, 执行用时: 39ms, 内存消耗: 4352KB, 提交时间: 2022-06-08
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int findLongestSubArray(vector<int>& nums) {
// write code here
int n=nums.size();
vector <int> dp_zheng(n,0),dp_fu(n,0);
vector <bool> positive(n,false);
if(nums[0]>0)
{
dp_zheng[0]=1;
positive[0]=true;
}
else if(nums[0]<0)
{
dp_fu[0]=1;
}
int res=0;
for(int i=1;i<n;i++)
{
if(nums[i]>0)
{
if(positive[i-1]==true)
{
dp_zheng[i]=dp_zheng[i-1]+1;
positive[i]=true;
}
else
{
dp_fu[i]=dp_fu[i-1]+1;
positive[i]=false;
}
}
else if(nums[i]<0) //<0
{
if(positive[i-1]==true)
{
dp_fu[i]=dp_zheng[i-1]+1;
positive[i]=false;
}
else
{
dp_zheng[i]=dp_fu[i-1]+1;
positive[i]=true;
}
}
else
{
dp_fu[i]=dp_zheng[i]=0;
positive[i]=true;
}
res=max(dp_zheng[i],res);
}
return res;
}
};