Cod sursa(job #395976)

Utilizator WildComunistChristian Ceausu WildComunist Data 14 februarie 2010 10:51:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

#define endl '\n' 

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

int n,v[100001],vl[100001],succ[100001];	
char s[1000010];

int main(){
	int i,j,lmax,imax;
	char *p;
	fin>>n;
	fin.get();
	fin.get(s,1000000);
	p=s;
	for(i=1;i<=n;i++){
		v[i]=atoi(p);
		while(*p!=' ') p++;
		p++;
	}
	//scanf("%d\n",&n);
	//fgets(
	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;
}