Cod sursa(job #2539084)

Utilizator Tudor06MusatTudor Tudor06 Data 5 februarie 2020 16:43:23
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>

using namespace std;

const int NMAX = 1e5;

int dp[NMAX]; /// lungimea scmax care se termina pe pozitia i
int v[NMAX];
int afisare[NMAX];

int main() {
    ifstream fin( "scmax.in" );
    ofstream fout( "scmax.out" );
    int n, i, maxim, cate, j;
    fin >> n >> v[0];
    dp[0] = 1;
    for ( i = 1; i < n; i ++ ) {
        fin >> v[i];
        for ( j = 0; j < i; j ++ ) {
            if ( v[j] < v[i] )
                dp[i] = max( dp[j], dp[i] );
        }
        dp[i] ++;
    }
    cate = 0;
    for ( i = 0; i < n; i ++ ) {
        cate = max( dp[i], cate );
    }
    fout << cate << '\n';
    maxim = 2e9 + 1;
    j = 0;
    for ( i = n - 1; i >= 0; i -- ) {
        if ( dp[i] == cate && v[i] < maxim ) {
            cate --;
            maxim = v[i];
            afisare[j] = v[i];
            j ++;
        }
    }
    for ( j --; j >= 0; j -- )
        fout << afisare[j] << ' ';
    return 0;
}