PTA:7-122 最长连续递增子序列 (20分)
程序员文章站
2022-03-13 16:46:41
...
7-122 最长连续递增子序列 (20分)
输入样例:
15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10
输出样例:
3 4 6 8
具体代码解释见AC代码:
#include<bits/stdc++.h>
using namespace std;
int a[100009];
queue<int> ans,q;
void clear(queue<int>& q){
queue<int> empty;
swap(empty,q);
}
int main(){
int n,cnt=0;
cin>>n;
for(int i=0; i<n; i++) cin>>a[i];
for(int i=0; i<n-1; i++){
if(a[i+1]<=a[i]){ //不连续递增了
q.push(a[i]);
if(q.size()>ans.size()){
clear(ans); //清空队列
while(!q.empty()){
ans.push(q.front());
q.pop();
}
}
clear(q);
}else{
q.push(a[i]);
}
}
if(a[n-1]>a[n-2]) q.push(a[n-1]); //上面的循环是到n-1的,所以这里要判断一下最后一个元素是否大于倒数第二个元素
//考虑到如果存在序列一直递增的到最后一个元素,则需要判断最后一个递增序列和之前的最大序列进行比较,取最大的那个
if(q.size()>ans.size()){
while(!q.empty()){
if(cnt) cout<<" ";
cout<<q.front();
cnt++;
q.pop();
}
}else{
while(!ans.empty()){
if(cnt) cout<<" ";
cout<<ans.front();
cnt++;
ans.pop();
}
}
return 0;
}
欢迎大家批评改正!!!
上一篇: 7-86 有几个ZUCC (25分)