Cod sursa(job #300167)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 7 aprilie 2009 11:50:32
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#define xy 100000
long long a[xy],l[xy],poz[xy],n;
void aranjare()
{
     long long i,j;
l[n]=1;poz[n]=-1;
      for(i=n-1;i>0;i--)
         for(l[i]=1, poz[i]=-1 ,j=i+1;j<=n;j++)
                    if(a[i]<=a[j] && l[i]<l[j]+1)
                               {l[i]=l[j]+1;poz[i]=j;
                               }
}
void max()
{//determin maximul din vectorul i
     long long i,max=l[1],pozmax=1;
         for( i=2;i<=n;i++)
           if(max<l[i]) {max=l[i];pozmax=i;}
 printf("%lld\n",max);
 for(i=pozmax;i!=-1;i=poz[i])
 printf("%lld ",a[i]);
}                                                 
int main()
{long long i;
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
  scanf("%lld",&n);
  for(i=1;i<=n;i++)
  scanf("%lld",&a[i]);
  aranjare();
  max();
 return 0;
}