Cod sursa(job #904814)

Utilizator profcntvProfCNTV profcntv Data 4 martie 2013 21:15:21
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
# include <cstdio>
# define Nmax 100001
using namespace std;

int a[Nmax], N, i, j, pozm;
int L[Nmax], poz[Nmax];
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]);
    L[N] = 1; poz[N] = -1; pozm = N;
    for (i=N-1; i>0; --i)
    {
        L[i] = 1; poz[i] = -1;
        for (j=i+1; j<=N; ++j)
            if (L[i]< 1 + L[j] && a[i]<a[j])
            {
                L[i] = 1 + L[j];
                poz[i] = j;
            }
        if (L[i]>L[pozm]) pozm = i;
    }

    printf("%d\n", L[pozm]);
    i = pozm;
    while (i!=-1)
    {
        printf("%d ", a[i]);
        i = poz[i];
    }
    return 0;
}