Cod sursa(job #2495761)

Utilizator CozminelDanielLupu Cosmin-Daniel CozminelDaniel Data 19 noiembrie 2019 20:03:09
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <bitset>
#include <iostream>

using namespace std;

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

int a[100002], urmator[100002], lis[100002], n;

int main()
{
    int maxim, poz;
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> a[i];
    fin.close();
    lis[n] = 1;
    urmator[n] = n + 1;
    for(int i = n - 1; i >= 1; i--)
    {
        maxim = 0;
        poz = n + 1;
        for(int j = i + 1; j <= n; j++)
            if(a[i] < a[j] && lis[j] > maxim)
            {
                maxim = lis[j];
                poz = j;
            }
        lis[i] = 1 + maxim;
        urmator[i] = poz;
    }
    poz = 1;
    for(int i = 2; i <= n; i++)
        if(lis[i] > lis[poz])
            poz = i;
    fout << lis[poz] << "\n";
    while(poz <= n)
    {
        fout << a[poz] << " ";
        poz = urmator[poz];
    }
    fout << "\n";
    fout.close();
    return 0;
}