交替正整数和负整数的最长切片
给定具有正值和负值的数组,返回最大连续切片大小,如果两个元素具有不同的符号,则返回两个元素交替,零被视为负值和正值。交替正整数和负整数的最长切片
例 鉴于a = [1, -5, 23, 0, 1, 1, 0, 2, -5, 3, -1, 1, 2, 3]
返回7
(序列[1, 0, 2, -5, 3, -1, 1]
具有最大交片大小)
预期运行时是O(n)
。
我试图解决像最大总和sequnce问题:
def sol(a):
n = len(a)
l = 0
left = 0
right = 0
tot = 1
for i in range(1,n):
if a[i]*a[i-1] > 0:
l = i + 1
else:
if i-l > right-left:
right = i
left = l
tot = max(tot,right-left+1)
return tot
我想这是一个错误的做法,但想不出其他
你的做法是好的,只是初始化一系列正常启动和清除过多的动作:
def sol(a):
l = 0
tot = 1
for i in range(1, len(a)):
if a[i]*a[i-1] > 0: #series violation
tot = max(tot, i - l)
l = i
return tot
我想我din't阅读问题正确。以下算法适用于子序列而非连续序列。
维持两个变量maxPositive
和maxNegetive
这保持了与正整数和负整数任何input[i]
结束最大片的长度。
伪代码
maxPositive = 0, maxNegetive = 0
answer = 1
for i: 1 to n
if(input[i] > 0)
maxPositive = max(maxPositive , maxNegetive + 1)
else if(input[i] < 0)
maxNegetive = max(maxNegetive , maxPositive + 1)
else
TempNegative = maxPositive + 1
TempPositive = maxNegetive + 1
maxPositive = max(maxPositive, TempPositive)
maxNegetive = max(maxNegetive , TempNegative)
int currentMax = max(maxPositive, maxNegative)
if(currentMax > answer)
answer = currentMax
return answer
我实现了这个算法,但它给了8以上输入:( – theSharpShooter
这里是上述实现的链接http://www.codeskulptor.org/#user43_VvShiuweQC_0.py – theSharpShooter
要知道,如果两个值是交替的符号(包括零)必须测试,如果这些值之间的差大于或比其absoulte值相等。换句话说,试试这个:
def sol(a): m = 0 for i in range(len(a)): j = i+1 while j<len(a): r = abs(a[j-1]-a[j]) if r<abs(a[j-1]) or r<abs(a[j]): break j+=1 if j-i>m: m=j-i return m
尝试这个 -
逻辑值维持一开始我们迭代,当我们的迭代中断时,我们只比较我们当前的最大长度和全局最大长度。
注 - 在迭代终止前,我们必须检查最后一次。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++){
int c;cin>>c;
v[i]=c;
}
int start=0;int maxlength=INT_MIN;
for(int i=1;i<n;i++){
if((v[i]>=0&&v[i-1]<=0)||(v[i]<=0&&v[i-1]>=0)){
if(i==n-1){
int length=i-start+1;
if(maxlength<length) maxlength=length;
}
}else{//
int length=i-start;
if(maxlength<length) maxlength=length;
start=i;
}
}
//cout<<start;
cout<<maxlength;
return 0;
}
你的具体问题是什么?展示你的努力来启动讨论。 – MBo
我也加了我的方法,对不起,最初@MBo – theSharpShooter
应该不是'1,-5,23,0,1,0,2,-5,3,1,1'是最长的片? – thebenman