Cod sursa(job #883629)

Utilizator DemnokStefan Demnok Data 20 februarie 2013 10:52:52
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
int a[100001],lg[100001],urm[100001],lgm,n,i,j,jm,im,nr;
int main ()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%ld",&n);
    lg[n]=1;
    urm[n]=0;

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

    for (i=n-1;i>=1;i--)
    {
        lgm=0;
        jm=0;

        for (j=i+1;j<=n;j++)
        {
            if(a[i]<=a[j]&& lg[j]>lgm)
            {
                lgm=lg[j];
                jm=j;
            }
        }

        lg[i]=lgm+1;
        urm[i]=jm;
    }

    lgm=0;
    for (i=1;i<=n;i++)
        if(lgm<lg[i]) lgm=lg[i],im=i;

    nr=0;
    i=im;
    do{
        nr++;
        i=urm[i];
    }while(i>0);
    printf("%ld\n",nr);
    do{
        printf("%ld ",a[im]);
        im=urm[im];
    }while(im>0);
    return 0;
}