Cod sursa(job #871722)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 5 februarie 2013 09:29:03
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define maxN 100005

int x[maxN] , dMax[maxN] , tata[maxN];
int last , solD , dim , sol[maxN];

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

    int N;

    scanf ("%d" , &N);

    for (int t = 1 ; t <= N ; ++t)
    {
        scanf ("%d" , &x[t]);

        int maxim = 0;

        for (int i = 1 ; i < t ; ++i)
            if (dMax[i] > maxim && x[i] < x[t])
            {
                maxim = dMax[i];
                tata[t] = i;
            }

        dMax[t] = maxim + 1;

        if (dMax[t] > solD)
        {
            solD = dMax[t];
            last = t;
        }
    }

    printf ("%d\n" , solD);
    for (int i = last ; i != tata[i] ; i = tata[i])
        sol[++dim] = x[i];

    for (int i = dim ; i >= 1 ; --i)
        printf ("%d " , sol[i]);

    return 0;
}