Cod sursa(job #464106)

Utilizator miculprogramatorA Cosmina - vechi miculprogramator Data 18 iunie 2010 20:25:52
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>

long long v[100001], l[100001];
int n, i, j, k;
int Max, t;
int ultim;

int main ()
{
    FILE *f = fopen ("scmax.in","r");
    FILE *g = fopen ("scmax.out","w");
    fscanf (f,"%d", &n);
    for (i=1; i<=n; ++i)
        fscanf (f,"%lld", &v[i]);

    l[n] = 1;
    for (k=n-1; k>=1; --k)
    {
        Max = 0;
        for (i=k+1; i<=n; ++i)
            if (v[i] > v[k] && l[i] > Max)
                Max = l[i];
        l[k] = Max + 1;
    }

    Max = l[1];
    t = 1;
    for (k=1; k<=n; ++k)
        if (l[k] > Max)
        {
            Max = l[k];
            t = k;
        }

    fprintf (g,"%d\n%d ", Max, v[t]);
    for (i=t+1; i<=n; ++i)
        if (v[i] > v[t] && l[i] == Max - 1)
        {
            fprintf (g,"%lld ", v[i]);
            Max --;
        }

    fclose(g);
    fclose(f);
    return 0;
}