题目描述

给定一个整数序列A1A2A3….An。求它的一个递增子序列，使子序列的元素个数尽量多，元素不一定要求连续。

输入格式

第1行：1个整数n(1<=n<=5000)，表示序列中元素的个数.

第2行-n+1行：每行1个整数x(-1000<=x<=1000)，第i+1行表示序列中的第i个元素。

输出格式

第1行：1个整数k，表示最长上升子序列的长度。

第2行：k个用单个空格分开的整数，表示找到了最长上升子序列。输出的是序列中的元素，并非下标。如果有多个长度等于k的子序列，则输出最靠前的1个。

样例

样例输入

复制8
1 3 2 4 3 5 4 6

样例输出

复制5
1 3 4 5 6

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

#include <bits/stdc++.h>
using namespace std;
int n,ans;
int a[100005];
int pre[100005];
int f[100005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=1;j<i;j++){
			if(a[j]<a[i]){
				if(f[j]+1>f[i]){
					f[i]=f[j]+1;
					pre[i]=j;
				}
			}
		}
	}
	int e;
	for(int i=1;i<=n;i++){
		if(f[i]>ans){
			ans=f[i];
			e=i;
		}
	}
	stack<int> s;
	while(e!=0){
		s.push(e);
		e=pre[e];
	}
	cout<<ans+1<<"\n";
	if(ans==0){
		cout<<a[1];
		return 0;
	}
	while(!s.empty()){
		cout<<a[s.top()]<<" ";
		s.pop();
	}
}