Cod sursa(job #2881687)

Utilizator vladutzu_finutzuVlad Cacenschi vladutzu_finutzu Data 30 martie 2022 18:47:17
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
vector<int> st, v, idx, s;
int n;
int main()
{
    cin>>n;
    v.resize(n);
    idx.resize(n);

    for(int i=0; i<n; i++)
        cin>>v[i];

    int sol = 0;
    for(int i=0; i<n; i++)
    {
        if(!st.size())
            st.push_back(v[i]), idx[i] = 0;
        
        else{
            int j = st.size() - 1;
            while(j >= 0 and st[j] >= v[i])
                j--;

            if(j + 1 == st.size())
                st.push_back(v[i]), idx[i] = j + 1;
            
            else st[j + 1] = v[i], idx[i] = j + 1;

            sol = max(sol, j + 1);
        }
    }
    cout<<sol + 1<<'\n';

    for(int i=n-1; i>=0; i--)
        if(idx[i] == sol)
            s.push_back(v[i]), sol--;
    
    reverse(s.begin(), s.end());

    for(int nr:s)
        cout<<nr<<" ";

    return 0;
}