Cod sursa(job #282948)

Utilizator cristiprgPrigoana Cristian cristiprg Data 18 martie 2009 16:07:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <cstdlib>
#define DIM 100002

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

void cmlsc()
{

    l[1] = 1;
    p[1] = -1;
    for (int i = 1; i <= n; i++)
    {
        l[i] = 1;
        p[i] = -1;
        for(int j = i - 1; j ; 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;

}
FILE *f = fopen("scmax.out", "w");

int ii;
void afis_rec(int poz)
{
    if(poz!=-1)
    {
        afis_rec(p[poz]);
        fprintf(f,"%d ",v[poz]);
    }
}

void afis()
{


    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];
    }
*/
    afis_rec(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;
}