Cod sursa(job #1329566)

Utilizator Burbon13Burbon13 Burbon13 Data 29 ianuarie 2015 17:23:36
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1 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 cacarnitza() ;
void rahatzire( int p ) ;

int main()
{
    freopen( "scmax.in" , "r" , stdin ) ;
    freopen( "scmax.out" , "w" , stdout ) ;
    khepis() ;
    printf( "%d\n" , mx + 1 ) ;
    rahatzire(  pp ) ;
    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 p )
{
    if ( ant[p] )
        rahatzire( ant[p] ) ;
    printf( "%d " , v[p] ) ;
}