Cod sursa(job #359735)

Utilizator petroMilut Petronela petro Data 28 octombrie 2009 10:37:50
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>
FILE *f=fopen("scmax.in","r");
FILE *g=fopen("scmax.out","w");

#define M 100000
long n,v[M],l[M],p[M];

void cit()
{
	long i;
	fscanf(f,"%ld",&n);
	for(i=1;i<=n;i++)
	    fscanf(f,"%ld",&v[i]);
		
	fclose(f);
}

int main()
{
	long i,j,max,poz,MAX=1,Poz;
	cit();
	
	l[n]=1;
	p[n]=-1;
	Poz=n;
	
	for(i=n-1;i>=1;i--)
	{
		max=0;
		for(j=i+1;j<=n;j++)
			if(v[i]<v[j]) if(l[j]>max) {max=l[j];
		                                poz=j;}
		l[i]=max+1;
		
		if(l[i]>MAX) {MAX=l[i];
		               Poz=i;}
		
		if(max!=0) p[i]=poz;
		else p[i]=-1;
	}
			
	fprintf(g,"%ld\n%ld ",MAX,v[Poz]);
		
	while(p[Poz]!=-1)
	{
		Poz=p[Poz];
		fprintf(g,"%ld ",v[Poz]);
	}
	fclose(g);
	return 0;
}