Cod sursa(job #1750761)

Utilizator daymon_cDumitru Chitoraga daymon_c Data 30 august 2016 22:21:05
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#define NMAX 100005

int best[NMAX], pos[NMAX], a[NMAX], n;

int main()
{
    freopen("scmax.in", "r", stdin);
    freopen("scmax.out", "w", stdout);

    scanf("%d", &n);

    for(int i=1; i<=n; ++i)
        scanf("%d", &a[i]);

    int bmax=0, pmax=0;
    for(int i=2; i<=n; ++i)
    {
        for(int j=1; j<i; ++j)
        {
            if (a[i]>a[j])
            {
                if(best[j]+1>best[i])
                {
                    best[i] = best[j] + 1;
                    pos[i] = j;
                }
            }
        }
        if(best[i] > bmax)
        {
            bmax = best[i];
            pmax = i;
        }
    }

    printf("%d\n", bmax+1);
    int i=0;
    while(pmax)
    {
        best[++i] = a[pmax];
        pmax = pos[pmax];
    }
    for(int j=i;j;--j) printf("%d ", best[j]);

    return 0;
}