Cod sursa(job #251889)

Utilizator RobybrasovRobert Hangu Robybrasov Data 3 februarie 2009 16:03:43
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <cstdio>
#define N 100001

int A[N],urm[N],C[N],n,i,j,max,pmax,maxt;

int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
    scanf("%d\n",&n);
    for (i=1; i<=n; i++) scanf("%d",&A[i]);
    C[n]=1; maxt=0;
    for (i=n-1; i; i--)
    {
        max=0;
        for (j=i+1; j<=n; j++)
            if (A[j]>A[i] && C[j]>max)
            {
                max=C[j];
                urm[i]=j;
            }
        C[i]=++max;
        if (max>maxt)
        {
            maxt=max;
            pmax=i;
        }
    }
    printf("%d\n",maxt);
    for (i=pmax; i; i=urm[i]) printf("%d ",A[i]);

    return 0;
}