Cod sursa(job #2119140)

Utilizator CryshanaGanea Carina Cryshana Data 31 ianuarie 2018 18:21:23
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 100001;
int v[N], pred[N], dp[N];

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

void subsir ( int p )
{
    if ( pred[p] != 0 )
        {
            subsir ( pred[p] );
        }
            fout << v[p] << " ";

}

int main()
{

    int pmax = 1, n;
    fin >> n;
    for ( int i = 1 ; i <= n ; i++ )
        fin >> v[i];
    for ( int i = 1 ; i <= n; i++ )
    {
        int lmax = 0;
        for ( int j = 1 ; j < i ; j ++ )
        {
            if ( v[j] < v[i] )
                {
                    if ( dp[j] > lmax )
                        {
                            lmax = dp[j];
                            pred[i] = j;
                        }
                }
        }
        dp[i] = 1 + lmax;
        if ( dp[i] > dp[pmax] )
        {
            pmax = i;
        }
    }
    fout << dp[pmax] <<"\n";
    subsir ( pmax );
    return 0;
}