Cod sursa(job #1268572)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 21 noiembrie 2014 01:51:00
Problema Subsir crescator maximal Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
FILE *fin, *fout;
int n, max;
long int *v;
struct tip
{
       int l;
       int x;
} *dyn;
void afisare(int a)
{
     if(dyn[a].x == -1) return;
     afisare(dyn[a].x);
     fprintf(fout, "%d ", v[a]);
}
int main()
{
    fin = fopen("scmax.in", "r");
    fout = fopen("scmax.out", "w");
    fscanf(fin, "%d", &n);
    v = new long int[n];
    dyn =  new tip[n];
    for(int i =0; i< n; i++) fscanf(fin, "%d", &v[i]);
    dyn[0].l = 1;
    dyn[0].x = -1;
    for(int i =1; i< n; i++)
    {
            dyn[i].l = 1;
            dyn[i].x = -1;
            for(int j = i-1; j>=0; j--)
            {
                    if(v[j] >= v[i]) continue;
                    if(dyn[j].l+1 > dyn[i].l)
                    {
                                  dyn[i].l = dyn[j].l+1;
                                  dyn[i].x = j;
                    }
            }
    }
    fprintf(fout, "%d\n", dyn[n-1].l);
    afisare(n-1);
    fclose(fin);
    fclose(fout);
    return 0;
}