Cod sursa(job #874642)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 9 februarie 2013 09:39:29
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 0.7 kb
#include<stdio.h>
int main()
{
    int n,a[100001],lmax,j,i,b[100001],vmax,k,p[100001],q,pmax;
    freopen("scmax.in","rt",stdin);
    freopen("scmax.out","wt",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    lmax=0;
    for(i=n;i>=1;i--)
    {
        vmax=0;
        q=0;
        for(j=i+1;j<=n;j++)
            if(a[i]<a[j] && b[j]>vmax)
               {
                   vmax=b[j];
                   q=j;
               }
        b[i]=1+vmax;
        p[i]=q;
        if(b[i]>lmax)
        {
            lmax=b[i];
            pmax=i;
        }
    }
    printf("%d\n",lmax);
    for(i=pmax;i;i=p[i])
        printf("%d ",a[i]);
    return 0;
}