Cod sursa(job #566879)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 29 martie 2011 13:05:26
Problema Subsir crescator maximal Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>
FILE *f=fopen("scmax.in","r");
FILE *g=fopen("scmax.out","w");
long int n,a[1001],v[1001];
long int L[1001],p[1001],max=0,emax;

int main(void){
	register long int i,j;

	fscanf(f,"%ld",&n);
	L[1]=1;
	fscanf(f,"%ld",&a[1]);
	p[1]=1;
	for(i=2;i<=n;i++){
		fscanf(f,"%ld",&a[i]);
		for(j=i-1;j>=1;j--){
		   if(a[j]<a[i])
			if(L[j]>L[i]){
				L[i]=L[j];
				p[i]=j;
			}
		}
		L[i]++;
		if(!p[i])
			p[i]=i;
		if(L[i]>max){
			max=L[i];
			emax=i;
		}
	}
	fclose(f);

	fprintf(g,"%ld\n",max);
	long int u=emax;
	long int q=1;
	v[1]=u;
	while(1){
		u=p[u];
		v[++q]=u;
		if(L[u]==1)
			break;
	}
	for(i=q;i>=1;i--){
		fprintf(g,"%ld ",a[v[i]]);
	}
	fclose(g);
	return 0;
}