Cod sursa(job #875890)

Utilizator horatiu11Ilie Ovidiu Horatiu horatiu11 Data 10 februarie 2013 21:39:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
# include <cstdio>
using namespace std;
long int N,i,a[10001],L[10001],poz[10001],j,pozm;
int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%ld",&N);
    for(i=1;i<=N;++i)
        scanf("%ld",&a[i]);
    L[N]=1;poz[N]=-1;pozm=N;
    for(i=N-1;i>0;i--)
    {
        L[i]=1;poz[i]=-1;
        for(j=i+1;j<=N;j++)
            if (L[i]<1+L[j] && a[i]<a[j])
            {
                L[i]=1+L[j];
                poz[i]=j;
            }
            if (L[i]>L[pozm]) pozm =i;
    }
    printf("%ld\n",L[pozm]);
    i=pozm;
    while (i!=-1)
    {
        printf("%ld ",a[i]);
        i=poz[i];
    }
    return 0;
}