Cod sursa(job #2458658)

Utilizator AndreosAndrei Otetea Andreos Data 21 septembrie 2019 11:55:24
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#define NMAX 100005
using namespace std;
int v[NMAX],l[NMAX],last[NMAX];
void afis(int i)
{
    if(last[i]!=0)
        afis(last[i]);
    printf("%d ",v[i]);
}
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    int n,i,j,maxl;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",v+i);
    //l[1]=1;
    maxl=1;
    for(i=1;i<=n;++i)
    {
        for(j=1;j<i;++j)
        {
            if(v[j]<v[i] && l[i]<l[j])
            {
                last[i]=j;
                l[i]=l[j];
            }
        }
        l[i]++;
        if(maxl<l[i])
            maxl=l[i];
    }
    /*
    for(i=1;i<=n;++i)
        printf("%d ",l[i]);
    printf("\n");*/
    i=n;
    while(l[i]!=maxl)
    {
        i--;
    }
    printf("%d\n",maxl);
    afis(i);
    printf("\n");
    return 0;
}