Cod sursa(job #2406477)

Utilizator vlad414141414141Vlad Ionescu vlad414141414141 Data 15 aprilie 2019 19:32:13
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

vector <int> v;
vector <int> lung;
vector <int> sol;

int main()
{
    int n;
    fin >> n;
    for (int i=0;i<n;++i)
    {
        int x;
        fin >> x;
        v.push_back(x);
    }
    lung.push_back(1);
    int megmax=0;
    for (int i=1;i<n;++i)
    {
        int maxim=0;
        maxim=0;
        for (int j=0;j<i;++j)
        {
            if (v[i]>v[j])
            {
                maxim=max(lung[j],maxim);
            }
        }
        lung.push_back(maxim+1);
        megmax=maxim+1;
    }
    fout << megmax << "\n";
    int c=0;
    for (int i=n-1;i>=0;i--)
    {
        if(lung[i]==megmax-c){
            sol.push_back(v[i]);
            c++;
        }
    }
    for (int i=sol.size()-1;i>=0;--i)
    {
        fout << sol[i] << " ";
    }
    return 0;
}