Cod sursa(job #268478)

Utilizator stefynr8Space Monkey stefynr8 Data 1 martie 2009 12:08:36
Problema Subsir 2 Scor 38
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>

long n,i,v[100001],p[100001],l[100001],j,max,first,min,a;
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);

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

first=n;
p[n]=-1;
l[n]=1;

for(i=n-1;i>=a;i--)
   {
   l[i]=1;
   p[i]=-1;

   for(j=i+1;j<=n;j++)
      {
      if((v[i]<=v[j]) && (l[i]<=l[j]+1)){
					p[i]=j;
					l[i]=l[j]+1;
					}

       }
   if(l[i]>max){ max=l[i];
		 first=i;
		 }

   }

printf("%ld\n",max);

i=first;
while(p[i]!=-1)
{
 printf("%ld ",v[i]);
 i=p[i];

}
printf("%ld",v[i]);
 return 0;
}