Cod sursa(job #2965889)

Utilizator SkaduweePavel Bogdan Stefan Skaduwee Data 16 ianuarie 2023 15:36:01
Problema Subsir crescator maximal Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 100000;
int n, v[NMAX+1], d[NMAX+1], len = 1, lenpoz = 0 ,last;
vector <int> sol;
int main()
{
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");

    fin >> n;
    for (int i = 0; i < n; i++){
        fin >> v[i];
        d[i] = 1;
        for (int j = 0; j < i; j++){
                if (v[j] < v[i])
                    d[i] = max(d[j] + 1, d[i]);
            }
        if (d[i] > len){
            lenpoz = i;
            len = d[i];
        }
    }
    fout << len << endl;
    sol.push_back(v[lenpoz]);
    for (int j = lenpoz-1; j > 0 && sol.size() != len; j--)
    {
        if (v[j] < sol[sol.size() - 1])
            sol.push_back(v[j]);
    }
    for (int i = len - 1; i >= 0; i--)
        fout << sol[i] << ' ';
    return 0;
}