Cod sursa(job #2891191)

Utilizator Luca_CristianZamfir Luca-Cristian Luca_Cristian Data 17 aprilie 2022 19:30:31
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
#define MAXN 100000
int best[MAXN], a[MAXN], prevv[MAXN];

void reconst(int poz)
{
    if(poz != -1)
    {
        reconst(prevv[poz]);
        fout << a[poz] << " ";
    }
}



int main()
{
    int  i, j, n, maxx, poz, maxxsir = 0, finall = 0;
    fin >> n;

    for(i = 0; i < n; i++)
    {
        fin >> a[i];
        maxx = 0;
        poz = -1;
        for(j = 0; j < i; j++)
            if(best[j] > maxx && a[j] < a[i])
            {
                maxx = best[j];
                poz = j;
            }
        best[i] = maxx + 1;
        prevv[i] = poz;
        if(best[i] > maxxsir)
        {
            maxxsir = best[i];
            finall = i;
        }
    }

    fout << maxxsir << "\n";
    reconst(finall);
    return 0;
}