Cod sursa(job #1974303)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 27 aprilie 2017 12:49:41
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <stack>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

const int NLIM = 1e5 + 10;

int N;

int v[NLIM];
int dp[NLIM];
int el[NLIM];

int eridx = 0;

int main()
{
    fin >> N;
    for( int i = 1; i <= N; ++i )
        fin >> v[i];

    dp[0] = 0;
    for( int i = 1; i <= N; ++i )
    {
        int hmax = 0;
        int hidx = 0;
        for( int j =  i - 1; j >= 0; --j )
        {
            if( v[i] > v[j] && dp[j] > dp[hidx] )
            {
                hidx = j;
            }
        }
        dp[i] = dp[hidx] + 1;
        el[i] = hidx;

        //cout << i << ": " << dp[i] << " " << el[i] << "\n";
        if( dp[i] > dp[eridx] )
        {
            eridx = i;
        }
    }


    stack< int > res;
    int hi = eridx;
    while( res.size() < dp[eridx] )
    {
        res.push( v[hi] );
        hi = el[hi];
    }

    fout << dp[eridx] << "\n";
    while( res.size() )
    {
        fout << res.top() << " ";
        res.pop();
    }
    fout << "\n";

    return 0;
}