Cod sursa(job #387802)

Utilizator Cristi09Cristi Cristi09 Data 28 ianuarie 2010 14:41:39
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<stdio.h>
int a[100000],best[100000],n,pos;
FILE*g=fopen("scmax.out","w");
void afis(int p)
{
   if(p>=n)return;
   if(best[p]==best[p-1])afis(p+1);
   else
   {fprintf(g,"%d ",a[p]);
	afis(p+1);}
}
int dinamic()
{
	best[n-1]=1;
	int i,j,max,LM=0;
	for(i=n-2;i>=0;--i)
	{
		max=0;
		for(j=i+1;j<n;++j)
		if(best[j]>max&&a[i]<a[j])
		{
			max=best[j];
			best[i]=max+1;
			if(LM<best[i]){LM=best[i];pos=i;}
		}
	}
	return LM;
}
int main()
{
	FILE*f=fopen("scmax.in","r");
	fscanf(f,"%d ",&n);
	int i;
	for(i=0;i<n;++i)
	fscanf(f,"%d",&a[i]);
	fclose(f);
	fprintf(g,"%d\n",dinamic());
	afis(pos);
	fclose(g);
}