Cod sursa(job #573268)

Utilizator dinuddinu dan dinud Data 6 aprilie 2011 09:16:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<stdio.h>

int l[100000],maxim,max,i,j,n,p,pmax,t[100000],v[100000];

FILE *f = fopen("scmax.in","r");
FILE *g = fopen("scmax.out","w");

void drum (int p){
	if(p!=0){
		drum(t[p]);
		fprintf(g,"%d ",v[p]);
	}
}

int main (){
	
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&v[i]);
	
	l[1]=1;
	for(i=2;i<=n;i++){
		max=0;
		p=0;
		for(j=1;j<i;j++)
			if(v[j]<v[i] && l[j]>max){
				max=l[j];
				p=j;
			}
		t[i]=p;
		l[i]=max+1;
		if(l[i]>maxim){
			maxim=l[i];
			pmax=i;
		}
	}
	fprintf(g,"%d\n",maxim);
	drum(pmax);
	
	fclose(f);
	fclose(g);
	return 0;
}