Cod sursa(job #2513938)

Utilizator traiandobrinDobrin Traian traiandobrin Data 24 decembrie 2019 10:56:31
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 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,maxb=1,indb=1;
    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;
        if(best[i]>maxb)
        {
            maxb=best[i];
            indb=i;
        }
    }
    cout<<best[indb]<<'\n';
    int cnt=best[indb];
    best[cnt+1]=-1;
    do{
            best[cnt]=indb;
            --cnt;
    indb=ex[indb];
    }while(indb);
    for(int i=1;best[i]!=-1;++i)
        cout<<v[best[i]]<<" ";
    return 0;
}