Cod sursa(job #1117362)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 23 februarie 2014 14:01:32
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>

using namespace std;

int V[100010], N, best[100010], poz[100010];

int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);

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

    for (i = 0; i < N; ++i)
        scanf("%d", &V[i]);

    best[N - 1] = 1;
    int maxnr, maxpz, max = 1, maxpoz;

    for (i = N - 2; i >= 0; --i)
    {
        maxnr = -(1 << 30);
        maxpz = N;
        for (j = i + 1; j < N; ++j)
        {
            if (V[i] < V[j] && maxnr < best[j])
            {
                maxnr = best[j];
                maxpz = j;
            }
        }
        best[i] = 1 + best[maxpz];
        poz[i] = maxpz;
        if (max < best[i])
        {
            max = best[i];
            maxpoz = i;
        }
    }

    printf("%d\n", max);

    printf("%d ", V[maxpoz]);
    for (i = maxpoz; i - maxpoz + 1 < max; ++i)
        printf("%d ", V[poz[i]]);
    printf("\n");

    fclose(stdout);
    return 0;
}