Cod sursa(job #2076009)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 25 noiembrie 2017 22:35:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
vector<int>q;
int n,v[100005],dp[100005],sl;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            if(v[i]>v[j])
                dp[i]=max(dp[i],dp[j]+1);
    for(int i=1;i<=n;i++)
        sl=max(sl,dp[i]);
    cout<<sl<<"\n";
    int dr;
    for(int i=1;i<=n;i++)
        if(dp[i]==sl)
        {
            dr=i;
            break;
        }
    for(int i=dr;i>=1;i--)
        if(dp[i]==sl)
        {
            q.push_back(i);
            sl--;
        }
    sl=q.size();
    for(int i=sl-1;i>=0;i--)
        cout<<v[q[i]]<<" ";
    return 0;
}