Cod sursa(job #282894)

Utilizator cristiprgPrigoana Cristian cristiprg Data 18 martie 2009 15:13:51
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <cstdlib>
#define DIM 100002

int v[DIM], l[DIM] = {-1}, p[DIM] = {1}, n;

void cmlsc()
{

    l[n] = 1;
    p[n] = -1;
    for (int i = n; i; i--)
    {
        l[n] = 1;
        p[n] = -1;
        for(int j = i + 1; j <= n; j++)
            if (v[i] < v[j] && l[i] < l[j] + 1)
                l[i] = l[j] + 1, p[i] = j;
    }
}

int max()
{


    int x = -1, ibun;
    for (int i = 1; i <= n; i++)
        if (x < l[i])
            x = l[i], ibun = i;

    return ibun;

}

void afis()
{

    FILE *f = fopen("scmax.out", "w");
 /*   int i;
    for (i = 1; i <= n; i++)
        printf ("%3d",v[i]);

    printf ("\n");
    for (i = 1; i <= n; i++)
        printf ("%3d",l[i]);

    printf ("\n");
    for (i = 1; i <= n; i++)
        printf ("%3d",p[i]);
*/
    int poz = max();
    fprintf (f, "%d\n", l[poz]);


    while (poz != -1)
    {
        fprintf (f, "%d ", v[poz]);

        //system("pause");
        poz = p[poz];
    }


    fclose(f);
}

int main()
{
    FILE *f = fopen("scmax.in", "r");
    fscanf(f, "%d", &n);

    int i;
    for (i = 1; i <= n; i++)
        fscanf(f, "%d", &v[i]);

    fclose(f);
    cmlsc();
    afis();

    return 0;
}