Cod sursa(job #395970)

Utilizator WildComunistChristian Ceausu WildComunist Data 14 februarie 2010 10:39:50
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream>
using namespace std;

#define endl '\n' 

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n,v[100001],vl[100001],succ[100001];	

int main(){
	int i,j,lmax,imax;
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i];
	vl[n]=1;
	for(i=n-1;i>=1;i--){
		lmax=1;
		for(j=i+1;j<=n;j++)
			if(v[i]<v[j]&&vl[j]>=lmax){
				lmax=vl[j]+1;
				succ[i]=j;
			}
		vl[i]=lmax;
	}
	lmax=0;
	for(i=1;i<=n;i++)
		if(vl[i]>lmax)
			lmax=vl[i],imax=i;
	fout<<lmax<<endl;
	i=imax;
	while(succ[i]){
		fout<<v[i]<<" ";
		i=succ[i];
	}
	fout<<v[i];
	return 0;
}