Cod sursa(job #1263263)

Utilizator ConstantinPetroviciPetrovici Constantin ConstantinPetrovici Data 14 noiembrie 2014 12:00:35
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <cstdio>

using namespace std;

int n , v [ 100007 ] , dp [ 100007 ] , maxim ;

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