Cod sursa(job #2301314)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 12 decembrie 2018 20:30:08
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#define lim_n 100001
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int n,i,j,maxx,k,l,coord;
int v[lim_n],pre[lim_n],best[lim_n],r[lim_n];
int main()
{
    in>>n;
    for(i=1;i<=n;++i)
    in>>v[i];
    best[1]=1;
    pre[1]=-1;
    l=1;
    coord=1;
    for(i=2;i<=n;++i)
    {
        maxx=0;
        k=-1;
        for(j=1;j<i;++j)
        if(v[j]<v[i]&&best[j]>maxx)
        {
            maxx=best[j];
            k=j;
        }
        pre[i]=k;
        best[i]=maxx+1;
        if(best[i]>l)
        {
            l=best[i];
            coord=i;
        }
    }
    out<<l<<endl;
    for(i=l;i>=1;--i)
    {
        r[i]=v[coord];
        coord=pre[coord];
    }
    for(i=1;i<=l;++i)
    out<<r[i]<<" ";

    return 0;
}