Cod sursa(job #509840)

Utilizator MarquiseMarquise Marquise Data 11 decembrie 2010 20:35:51
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>

#define NMAX 100001

int n, v[NMAX], pred[NMAX], m[NMAX];


void secventa()
{
    int i, j, pmax;

    for ( i = n - 1; i >= 0; i--)
    {
        m[i] = 1;
        pred[i] = -1;
        for ( j = i + 1; j < n; j++)
            if ( v[j] > v[i] && m[j] + 1 > m[i])
            {
                m[i] = m[j] + 1;
                pred[i] = j;
            }

    }
    pmax = 0;
    for ( i = 1; i < n; i++)
        if ( m[i] > m[pmax])
            pmax = i;

    printf("%d\n", m[pmax]);
    for ( i = 1, j = pmax; i <= m[pmax]; i++)
    {
        printf("%d ", v[j]);
        j = pred[j];
    }


}


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

    scanf("%d", &n);
    for ( i = 0; i < n; i++)
        scanf("%d", &v[i]);

    secventa();

    return 0;
}