Cod sursa(job #2546369)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 14 februarie 2020 09:26:57
Problema Subsir crescator maximal Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;
vector<int>v;
int val[100005];
int poz[100005];
int n,i;
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d%d",&n,&i);
    int cnt=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        int nr=val[i];
        if(v.empty()){v.push_back(nr);poz[1]=1;cnt=1;}
        else
        {
            vector<int>::iterator it;
            it=lower_bound(v.begin(),v.end(),nr);
            if(it==v.end())
            {
                v.push_back(nr);
                poz[i]=++cnt;
            }
            else
                v[it-v.begin()]=nr,poz[i]=it-v.begin()+1;
        }
    }
    cout<<cnt<<endl;
    stack<int>st;
    for(i=n;i>=1;--i)
    {
        if(poz[i]==cnt)
        {
            st.push(val[i]);
            --cnt;
        }
    }
    while(!st.empty())
    {
        cout<<st.top()<<" ";
        st.pop();
    }
    return 0;
}