Cod sursa(job #2601812)

Utilizator betybety bety bety Data 15 aprilie 2020 11:35:14
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
#include <climits>
#include <stack>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
stack<int> q;
const int lim=1e5+3;
int v[lim],last[lim],dp[lim];
vector<int> sol;
int main()
{
    int n,ind,answer=INT_MIN;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>v[i];
        while(!q.empty() and v[q.top()]>=v[i])
            q.pop();
        if(q.empty()) dp[i]=1,last[i]=-1;
        else dp[i]=dp[q.top()]+1,last[i]=q.top();
        if(dp[i]>answer)
        {
            answer=dp[i];
            ind=i;
        }
        q.push(i);
    }
    cout<<answer<<'\n';
    for(int i=1;i<=answer;++i)
    {
        sol.push_back(v[ind]);
        ind=last[ind];
    }
    for(int i=sol.size()-1;i>=0;--i)
        cout<<sol[i]<<' ';
    return 0;
}