Cod sursa(job #387403)

Utilizator nandoLicker Nandor nando Data 27 ianuarie 2010 16:08:03
Problema Subsir crescator maximal Scor 35
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <iostream>

#define MAX 100000
#define MAXB 8192

using namespace std;

char buf[MAXB];
unsigned ptr=0;

FILE* fin=fopen("scmax.in","rb");

int getInt(){
	while(buf[ptr]<'0'||'9'<buf[ptr]){
		if(++ptr>=MAXB){
			fread(buf,1,MAXB,fin);
			ptr=0;
		}
	}
	int nr=0;
	while('0'<=buf[ptr]&&buf[ptr]<='9'){
		nr=nr*10+buf[ptr]-'0';
		if(++ptr>=MAXB){
			fread(buf,1,MAXB,fin);
			ptr=0;
		}
	}
	return nr;
}
int main(){
	fstream fout("scmax.out",ios::out);
	fread(buf,1,MAXB,fin);
	
	int vec[MAX],vP[MAX],v[MAX],res[MAX];
	
	int n,imax=0,k,p=0;
	
	vP[0]=-1;
	v[0]=1;
	n=getInt();
	for(int i=0;i<n;i++){
		vec[i]=getInt();
	}
	for(int i=n-1;i>=0;--i){
		vP[i]=-1;
		v[i]=1;
		for(int j=i+1;j<n;++j){
			if(vec[j]>vec[i]&&v[j]+1>v[i]){
				v[i]=v[j]+1;
				vP[i]=j;  
			}
		}
		if(v[i]>v[imax]){
			imax=i;
		}
	}
	fout<<v[imax]<<endl;
	k=imax;
	while(vP[k]!=-1){
		cout<<vec[k]<<" ";
		k=vP[k];
	}
	fout<<vec[k]<<" ";
	fclose(fin);
	fout.close();
}