Cod sursa(job #461932)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 9 iunie 2010 11:05:51
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;

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

int const N=1<<17;
int n,v[N],lung[N],pred[N];

void attach(int i){
	int j,maxx=0,predsec=0;
	for(j=1;j<=i;j++){
		if(v[i]>v[j]){
			if(lung[j]>maxx){
				maxx=lung[j];
				predsec=j;
			}
		}
	}
	if(maxx==0){
		lung[i]=1;
		pred[i]=0;
		return;
	}
	lung[i]=1+maxx;
	pred[i]=predsec;
	return;
}

void scriere(int i){
	if(pred[i]==0){
		out<<v[i]<<" ";
		return;
	}
	scriere(pred[i]);
	out<<v[i]<<" ";
}

void prelucrare(){
	int i,maxl=0,maxx=0;
	lung[1]=1;
	pred[1]=0;
	for(i=2;i<=n;i++){
		attach(i);
		if(maxl<lung[i]){
			maxx=i;
		}
	}
	out<<lung[maxx]<<"\n";
	scriere(maxx);
}

int main(){
	in>>n;
	for(int i=1;i<=n;i++){
		in>>v[i];
	}
	prelucrare();
	return 0;
}