Cod sursa(job #491217)

Utilizator chrissBota Cristian chriss Data 10 octombrie 2010 18:53:25
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>

int a[100100],grozav[100100],urmator[100100],n,max,lmax,pi,i,j;

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);

    scanf("%d",&n);
    for(i=1; i<=n; ++i)
        scanf("%d",&a[i]);
    grozav[n]=1;
    for(i=n-1; i>=1; --i)
    {
        max=0;
        for(j=i+1; j<=n; ++j)
            if((a[j]>a[i])&&(max<grozav[j]))
            {
                max=grozav[j];
                urmator[i]=j;
            }
        grozav[i]=max+1;
        if (lmax<grozav[i])
        {
            lmax=grozav[i];
            pi=i;
        }
    }
    printf("%d\n",lmax);
    printf("%d ",a[pi]);
    for(i=pi; urmator[i]!=0; urmator[i]=urmator[urmator[i]])
        printf("%d ",a[urmator[i]]);
    return 0;
}