Cod sursa(job #2255200)

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

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

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

    int N;
    scanf("%i", &N);

    int *vect = (int*)malloc(N * sizeof(int));
    for(int i = 0; i < N; ++i)
        scanf("%i", vect + i);
    int *maxlen = (int*)malloc(N * sizeof(int));
    int *prevpos = (int*)malloc(N * sizeof(int));

    int maxlenVal = 0;
    int maxlenPos = N;
    for(int i = N - 1; i >= 0; --i)
    {
        maxlen[i] = 1;
        prevpos[i] = N;
        for(int j = N - 1; j > i; --j)
            if(vect[i] < vect[j] && maxlen[j] + 1 > maxlen[i])
            {
                maxlen[i] = maxlen[j] + 1;
                prevpos[i] = j;
            }

        if(maxlen[i] > maxlenVal)
        {
            maxlenVal = maxlen[i];
            maxlenPos = i;
        }
    }

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

    int p = maxlenPos;
    while(p != N)
    {
        printf("%i ", vect[p]);
        p = prevpos[p];
    }

    return 0;
}