Cod sursa(job #268479)

Utilizator andumMorie Daniel Alexandru andum Data 1 martie 2009 12:11:31
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>

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

int main()
{

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

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

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