Cod sursa(job #929753)

Utilizator JacketDumitrascu Constantin Jacket Data 27 martie 2013 11:04:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
using namespace std;

#define NMAX    100001

#define inFile  "scmax.in"
#define outFile "scmax.out"

void Citire(), Afisare();

int a[NMAX], n, m, x;

int main() {
    Citire();
    Afisare();

    return 0;
}

void Citire() {
    freopen( inFile, "r", stdin );
    scanf( "%d", &n );
    for( int i = 1; i <= n; i++ ) {
        scanf( "%d", &a[i] );
    }
}

void Afisare() {

    int i, j,
        *val = new int[n+1],
        *poz = new int[n+1];
    for( i = n; i > 0; i-- ) {

        val[i]  = 1;
        poz[i] = -1;
        for( j = i+1; j <= n; j++ ) {

            if( a[i] < a[j] && val[i] <= val[j] ) {

                val[i] = val[j];
                poz[i] = j;

            }
        }
        if(poz[i]!=-1)
            val[i]++;
    }

    for( i = 1; i <= n; i++ ) {

        if( m < val[i] ) {

            m = val[i];

            x = i;

        }
    }

    freopen( outFile, "w", stdout );

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

    for( i = x; i != -1; i = poz[i] ) {
        printf( "%d ", a[i] );
    }

    printf("\n");

}