Cod sursa(job #2557494)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 25 februarie 2020 20:38:53
Problema Subsir crescator maximal Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 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 stop = 0;
        lis[i] = 1;

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

            if ( sir[j] > sir[i] && lis[i] < lis[j] + 1 ) {

                lis[i] = lis[j] + 1;

            } else if ( sir[j] == sir[i] ) {

                lis[i] = lis[j];

            }

        }

    }

    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;

        }

    }

    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;
}