Cod sursa(job #2255213)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 6 octombrie 2018 16:37:59
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
/*
NAME: Petru Ciocirlan
TASK: scmax
LANG: C++
*/
#include <cstdio>
#include <cstdlib>

#define FILE_IN "scmax.in"
#define FILE_OUT "scmax.out"

const int MAXN = 100000 + 16;
int N, vect[MAXN], best[MAXN], prev[MAXN];

int main()
{
    freopen(FILE_IN, "r", stdin);
    freopen(FILE_OUT, "w", stdout);

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

    int bestPos, bestVal;
    bestVal = bestPos = 0;

    for(int i = 1; i <= N; ++i)
    {
        best[i] = 1;
        prev[i] = 0;

        for(int j = 1; j < i; ++j)
            if(vect[j] < vect[i] && best[j] + 1 > best[i])
        {
            best[i] = best[j] + 1;
            prev[i] = j;
        }

        if(best[i] > bestVal)
        {
            bestVal = best[i];
            bestPos = i;
        }
    }

    printf("%i\n", bestVal);

    int coada[MAXN], k;
    k = 0;
    while(bestPos)
    {
        coada[++k] = vect[bestPos];
        bestPos = prev[bestPos];
    }

    for(int i = k; i; --i)
        printf("%i ", coada[i]);

    return 0;
}