Cod sursa(job #457698)

Utilizator remustataRemus Gabriel remustata Data 20 mai 2010 23:38:21
Problema Subsir crescator maximal Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <stdlib.h>

int n,imax;
long a[100002];
long lung[100002];
long poz[100002];

FILE *in,*out;

void read()
{
	int i;

	in=fopen("scmax.in","r");
	fscanf(in,"%d",&n);

	printf("n=%d",n);
	for(i=0;i<n;i++)
		fscanf(in,"%d",&a[i]);
	
}

void prelucreaza()
{
	int i,j;
	lung[0]=1;
	imax=0;
	poz[0]=-1;	
	for(i=0;i<n;i++)
	{
		lung[i]=1;
		poz[i]=-1;
		for	(j=0;j<i;j++)
			if(a[j]<a[i]&&lung[j]+1>lung[i])
			{
				lung[i]=lung[j]+1;
				poz[i]=j;			
			}
		if(lung[i]>lung[imax])
			imax=i;
	}
	
}

void rec(int i)
{
	if(poz[i]+1)
		rec(poz[i]);
	fprintf(out,"%d ",a[i]);
	
}

void write()
{
	fprintf(out,"%d\n",lung[imax]);
	rec(imax);
}

int main()
{
	out=fopen("scmax.out","w");
	read();
	prelucreaza();
	write();


}