Cod sursa(job #2513937)

Utilizator traiandobrinDobrin Traian traiandobrin Data 24 decembrie 2019 10:51:50
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#define lim 100005
using namespace std;
int v[lim],best[lim],ex[lim];
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int main()
{
    int n;
    cin>>n>>v[1];
    best[1]=1;
    for(int i=2;i<=n;++i)
    {
        cin>>v[i];
        int maxx=0,ind=0;
        for(int j=1;j<i;++j)
        {
            if(v[j]<v[i]){
                if(maxx<best[j])
                {
                    maxx=best[j];
                    ind=j;
                }
            }
        }
        best[i]=1+maxx;
        ex[i]=ind;
    }
    cout<<best[n]<<'\n';
    int cnt=best[n];
    best[cnt+1]=-1;
    do{
            best[cnt]=n;
            --cnt;
    n=ex[n];
    }while(n);
    for(int i=1;best[i]!=-1;++i)
        cout<<v[best[i]]<<" ";
    return 0;
}