Cod sursa(job #697029)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 28 februarie 2012 21:43:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>
#define LL long long
#define MV 100004
using namespace std;
const char iname[] = "scmax.in";
const char oname[] = "scmax.out";
ifstream f(iname); ofstream g(oname);
int i, n, j;
int lmax, p;
int best[MV], v[MV], poz[MV];
int main(){
	f>>n; for( i = 1; i <= n; ++i ) f>>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;
			}
	}
	g<<lmax<<'\n'; i=p;
	while( i != -1 ){
		g<<v[i]<<' ';
		i=poz[i];
	}
	g<<'\n';
	return 0;
}