Cod sursa(job #878211)

Utilizator mazaandreiAndrei Mazareanu mazaandrei Data 14 februarie 2013 09:48:52
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include<fstream>
#define nmax 100005
using namespace std;
int best[nmax],poz[nmax],lmax,p,n,v[nmax],i,j;
int main(){
	ifstream in("scmax.in"); ofstream out("scmax.out");
	in>>n;
	for(i=1;i<=n;++i) in>>v[i];
	best[n]=1; poz[n]=-1; lmax=1; p=n;
	for(i=n-1;i>=1;--i){
		best[i]=1; poz[i]=-1;
		for(j=i+1;j<=n;++j){
			if(v[i]<v[j] && best[i]<best[j]+1){
				best[i]=best[j]+1; poz[i]=j;
				if(best[i]>lmax) lmax=best[i], p=i;
			}
		}
	}
	out<<lmax<<'\n'; i=p;
	while(i!=-1){
		out<<v[i]<<' ';
		i=poz[i];
	}
	out<<'\n';
	out.close(); return 0;
}