Cod sursa(job #1466757)

Utilizator mariakKapros Maria mariak Data 30 iulie 2015 10:48:38
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <algorithm>
#define Dim 100003
FILE * f = fopen("scmax.in", "r");
FILE * g = fopen("scmax.out", "w");

using namespace std;
int n, i, best[Dim], poz[Dim], p, a[Dim], maxx;
void read()
{
    fscanf(f, "%d", &n);
    for(i = 1; i <= n; ++ i)
        fscanf(f, "%d", &a[i]);
}
void DP()
{
    int i, j;
    best[n] = 1;
    poz[n] = -1;
    p = n;
    maxx = 1;
    for(i = n - 1; i >= 1; -- i)
    {
        best[i] = 1;
        poz[i] = -1;
        for(j = i + 1; j <= n; j ++)
            if(a[j] > a[i] && best[i] < best[j] + 1)
        {
            best[i] = best[j] + 1;
            poz[i] = j;
            if(maxx < best[i])
                maxx = best[i], p = i;
        }
    }

}
void build()
{
    int i;
    i = p;
    while(i != -1)
    {
        fprintf(g, "%d ", a[i]);
        i = poz[i];
    }
}
int main()
{
    read();
    DP();
    fprintf(g, "%d\n", maxx);
    build();
    return 0;
}