欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA:7-122 最长连续递增子序列 (20分)

程序员文章站 2022-03-13 16:46:41
...

7-122 最长连续递增子序列 (20分)

PTA: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;
} 

欢迎大家批评改正!!!