Cod sursa(job #180466)

Utilizator eugen.nodeaEugen Nodea eugen.nodea Data 17 aprilie 2008 08:35:47
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.52 kb
# include <stdio.h>
long a[100000],N,i,j,m;
int main()
{
  long L[100000],poz[100000];
  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; poz[N]=-1;m=N;
  for (i=N-1;i>0;i--){
	 L[i]=1; poz[i]=-1;
	  for (j=i+1;j<=N;j++)
		if (L[i]<1+L[j] && a[i]<a[j]) {
		  L[i]=1+L[j];
		  poz[i]=j;
		}
	if (L[i]>L[m]) m=i;
  }
  printf("%ld\n",L[m]);
  i=m;
  while (i!=-1){
	 printf("%ld ",a[i]);
  i=poz[i];
  }
  return 0;
}