Cod sursa(job #2217240)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 29 iunie 2018 18:05:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <cstdlib>
#define FIN "scmax.in"
#define FOUT "scmax.out"
#define MAXN 100005
int N, v[MAXN], pd[MAXN], poz[MAXN], idx;

int main()
{
    freopen(FIN, "r", stdin);
    freopen(FOUT,"w", stdout);

    scanf("%i", &N);
    for(int i = 1; i <= N; ++i)
        scanf("%i", v+i);

    pd[N] = 1, poz[0] = 1, idx = N;
    for(int i = N-1; i; --i)
    {
        pd[i] = 1;
        for(int j = N; j > i; --j)
            if(v[i] < v[j] && pd[i] < pd[j] +1)
                pd[i] = pd[j] +1, poz[i] = j;
        if(pd[i] > pd[0])
        {
            pd[0] = pd[i];
            idx = i;
        }
    }
    int k = 0;
    while(idx)
    {
        pd[++k] = v[idx];
        idx = poz[idx];
    }
    printf("%i\n", k);
    for(int i = 1; i <= k; ++i)
        printf("%i ", *(pd+i));
    putchar('\n');

    return 0;
}