Cod sursa(job #1282031)

Utilizator NeapoleonDan-Mihai Bradu Neapoleon Data 3 decembrie 2014 21:57:42
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream cin("scmax.in");
ofstream cout("scmax.out");

int a[100005],b[100005],c[100005],i,j,n,mx,p;

int main()
{
	cin>>n;
	for(i=1;i<=n;++i)cin>>a[i];
	b[n]=1;
	c[n]=-1;
	mx=1;
	p=n;
	for(i=n;i>=1;--i){
		b[i]=1;
		c[i]=-1;
		for(j=i+1;j<=n;++j){
			if(a[i]<a[j] && b[i]<b[j]+1){
				b[i]=b[j]+1;
				c[i]=j;
				if(b[i]>mx)mx=b[i],p=i;
			}
		}
	}
		cout<<mx<<'\n';
		i=p;
		while(i!=-1){
			cout<<a[i]<<' ';
			i=c[i];
	}
	
	return 0;
}