Cod sursa(job #185773)

Utilizator NicholasDragos Nicolae Nicholas Data 26 aprilie 2008 00:02:55
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
int a[100001],b[100001],c[100001],n,i,j,poz,max;
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]);
     
     for (i=n;i>=1;i--)
        {
         b[i]=1; c[i]=-1;
         for (j=i;j<=n;j++)
           if (a[i]<a[j] && b[i]<b[j]+1)
                      {b[i]=b[j]+1;
                       c[i]=j;
                       }
        }               
     max=b[1];
     for (i=1;i<=n;i++)
         if (max<b[i]) {max=b[i]; poz=i;}
     printf("%ld\n",max);
     while (poz!=-1)
          {
              printf("%ld ",a[poz]);
              poz=c[poz];
          }
     fclose(stdin);
     fclose(stdout);    
     return 0;
}