Cod sursa(job #1663090)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 25 martie 2016 15:27:34
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#define INF 100010

using namespace std;

int v[INF], l[INF], u[INF];

int main()
{
    freopen ( "scmax.in", "r", stdin );
    freopen ( "scmax.out", "w", stdout );
    int n, i, j, maxj, in;
    scanf ( "%d", &n );
    for ( i = 1; i <= n; ++i )
        scanf( "%d", &v[i] );
    l[n] = 1;
    for ( i = n - 1; i > 0; --i )
    {
        maxj = 0, in = 0;
        for ( j = n; j > i; --j )
            if ( v[i] < v[j] && l[j] >= maxj )
                maxj = l[j], in = j;
        l[i] = maxj + 1;
        u[i] = in;
    }
    maxj = 0;
    for ( i = 1; i <= n; ++i )
        if ( l[i] > maxj )
            maxj = l[i], in = i;
    printf ( "%d\n", maxj );
    while ( u[in] != 0 )
        printf ( "%d ", v[in] ), in = u[in];
    printf ( "%d ", v[in] );
    return 0;
}