Cod sursa(job #2557519)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 25 februarie 2020 20:48:44
Problema Subsir crescator maximal Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int sir[100005], lis[100005];
int n;

/// lis[i] = 1 + max(lis[j]), unde j>i si a[j] > a[i]
/// completarea se face de la dreapta la stanga
/// for ( i = n ... )

int main()
{

    fin >> n;

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

        fin >> sir[i];

    }

    lis[n] = 1;

    for ( int i = n - 1; i >= 1; --i ) {

        int maxim = 0;

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

            if ( sir[j] > sir[i] ) {

                maxim = max(maxim, lis[j]);

            }

        }

        lis[i] = maxim + 1;

    }

    int maxim = lis[1], p = 1, val = sir[1];

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

        if ( maxim < lis[i] ) {

            maxim = lis[i];
            val = sir[i];
            p = i;

        }

        //cout << lis[i] << " ";

    }

    fout << maxim << "\n";

    fout << val << " ";

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

        if ( sir[i] > val ) {

            fout << sir[i] << " ";
            val = sir[i];

        }

    }

    return 0;
}