Cod sursa(job #1329558)

Utilizator Burbon13Burbon13 Burbon13 Data 29 ianuarie 2015 17:12:35
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <cstdio>
#define n_max 100005

using namespace std;

int n , v[n_max] , ant[n_max] , val[n_max] , pp , mx ;

void khepis() ;
void rahatzire() ;

int main()
{
    freopen( "scmax.in" , "r" , stdin ) ;
    freopen( "scmax.out" , "w" , stdout ) ;
    khepis() ;
    rahatzire() ;
    return 0;
}

void cacarnitza( int pos )
{
    for ( int j = pos - 1 ; j > 0 ; j -- )
        if ( v[j] < v[pos] && val[j] + 1 > val[pos] )
        {
            ant[pos] = j ;
            val[pos] = val[j] + 1 ;
        }
}

void khepis()
{
    val[0] = -1 ;
    scanf( "%d" , &n ) ;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        scanf( "%d" , &v[i] ) ;
        cacarnitza(i) ;
        if ( val[i] > mx )
        {
            mx = val[i] ;
            pp = i ;
        }
    }
}

void rahatzire()
{
    int rez[n_max] , pos = 0 ;
    while ( val[pp] >= 0 )
    {
        rez[++pos] = v[pp] ;
        pp = ant[pp] ;
    }
    printf( "%d\n" , mx + 1 ) ;
    for ( int i = pos ; i > 0 ; i -- )
        printf( "%d " , rez[i] ) ;
}