Cod sursa(job #2672821)

Utilizator Gliumarin negai Gliu Data 14 noiembrie 2020 22:56:58
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.56 kb
//#include <iostream>
#include <fstream>

using namespace std;
typedef long long ll;

ifstream cin("scmax.in");
ofstream cout("scmax.out");
const ll NMAX=100009;
ll a[NMAX],b[NMAX],n,ans,k,t[NMAX],pp,p;


int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
b[n]=1;t[n]=0;
for(int i=n-1;i>0;i--){
	b[i]=1;t[n]=0;
	for(int j=i+1;j<=n;j++){
		if(a[i]<a[j] && b[i]<b[j]+1){
			b[i]=b[j]+1;
			t[i]=j;
		}
		   
		if(b[i]>ans){
			pp=i;
			ans=b[i];
		}  
	}
}
p=pp;
cout<<ans<<"\n";
do{
	cout<<a[p]<<" ";
	p=t[p];
}while(p!=0);

return 0;
}