Cod sursa(job #1046193)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 2 decembrie 2013 18:55:04
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include<stack>

using namespace std;


stack<int> my_stack;
int v[100001], best[100001], stpoz[100001];

int main () {

    FILE *f, *g;
    f = fopen( "scmax.in", "r" );
    g = fopen( "scmax.out", "w" );

    int n, max, elmax = 0, poz, p;

    fscanf( f, "%d", &n );

    for( int i = 0 ; i < n ; ++i )
        fscanf( f, "%d", &v[i] );

    best[0] = 1;
    elmax = -1;

    for( int i = 1 ; i < n ; ++i ) {
        max = 0;

        for( int j = i - 1 ; j >= 0 ; --j ) {
            if( best[j] > max  && v[j] < v[i])
                max = best[j];
        }

        best[i] = max + 1;
        if( best[i] > elmax )
            elmax = best[i], poz = i;
    }


    my_stack.push(v[poz]);
    elmax--;
    int val_max = v[poz];

    for( int i = poz - 1 ; i >= 0 ; --i ) {
        if( best[i] != elmax || v[i] >= val_max)
            continue;
        my_stack.push(v[i]);
        val_max = v[i]; elmax--;
    }

    fprintf( g, "%d\n", my_stack.size() );

    while( my_stack.size()) {
        fprintf( g, "%d ", my_stack.top() );
        my_stack.pop();
    }

    fclose( f );
    fclose( g );

    return 0;

}