Cod sursa(job #1982849)

Utilizator CleliaClelia Maria Dobrescu Clelia Data 20 mai 2017 13:44:29
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
int a[100001],d[100001],v[100001],r[100001];
int main (){
    freopen ("scmax.in","r",stdin);
    freopen ("scmax.out","w",stdout);
    int maxx=0,n,i,maxi,j,poz,pozi;
    scanf ("%d",&n);
    for (i=1;i<=n;i++){
        maxi=0;
        scanf ("%d",&a[i]);
        for (j=1;j<i;j++)
            if (a[j]<a[i])
                if (maxi<d[j]){
                    maxi=d[j];
                    poz=j;
                }
        d[i]=maxi+1;
        v[i]=poz;
        if (maxx<d[i]){
            maxx=d[i];
            pozi=i;
        }
    }
    for (i=1;i<=maxx;i++){
        r[maxx-i+1]=a[pozi];
        pozi=v[pozi];
    }
    printf ("%d\n",maxx);
    for (i=1;i<=maxx;i++)
        printf ("%d ",r[i]);
    return 0;
}