Cod sursa(job #2247410)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 28 septembrie 2018 16:16:30
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <iostream>
using namespace std;

#define NMAX 100005

int A[ NMAX ], D[ NMAX ], P[ NMAX ];

void sir( int i ) {

    if ( P[ i ] != 0 ) {
        sir( P[ i ] );
    }
    printf( "%d ", A[ i ] );

}

int main () {

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

    int n, i, j, m, k, ma;
    ma = 0;

    scanf( "%d", &n );
    for ( i = 1; i <= n; ++i ) {
        scanf( "%d", &A[ i ] );
        D[ i ] = 1;
    }

    for ( i = 2; i <= n; ++i ) {
        for ( j = 1; j < i; ++j ) {
            if ( A[ i ] > A[ j ] && D[ j ] + 1 > D[ i ] ) {
                D[ i ] = D[ j ] + 1;
                P[ i ] = j;
            }
        }
        ma = max( ma, D[ i ] ) ;
    }

    printf( "%d\n", ma );
    for ( i = n; i >= 1; --i ) {
        if ( D[ i ] == ma ) {
            sir( i );
            i = 0;
        }
    }

    return 0;

}