Cod sursa(job #241651)

Utilizator andumMorie Daniel Alexandru andum Data 10 ianuarie 2009 16:46:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <stdio.h>

FILE *f,*g;

long a[100001],l[100001],p[100001],i,j,n,max,x;

int main()
{

 freopen("scmax.in","r",stdin);
 freopen("scmax.out","w",stdout);

 scanf("%ld", &n);
 for (i=1;i<=n;i++)
	scanf("%ld", &a[i]);

 l[n]=1; p[n]=-1;
 for (i=n-1;i>=1;i--)
	{
	 l[i]=1;
	 p[i]=-1;
	 for (j=i+1;j<=n;j++)
		if (a[i]<a[j] && l[i]<l[j]+1)
			{
			 l[i]=l[j]+1;
			 p[i]=j;
			}
	 if (l[i]>max)
		{
		 max=l[i];
		 x=i;
		}
	}
 printf("%ld\n", max);
 i=x;
 while (p[i]!=-1)
	{
	 printf("%ld ", a[i]);
	 i=p[i];
	}
 printf("%ld", a[i]);

 return 0;

}