Cod sursa(job #1674935)

Utilizator preda.andreiPreda Andrei preda.andrei Data 4 aprilie 2016 22:54:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <cstdio>

using namespace std;

int v[200001];
int lungime[200001];
int predecesor[200001];

void refa(int p, FILE *f);

int main()
{
    FILE *fin = fopen("scmax.in", "r");
    FILE *fout = fopen("scmax.out", "w");

    int n, poz = 0;

    fscanf(fin, "%d", &n);
    for(int i = 1; i <= n; ++i){
        fscanf(fin, "%d", &v[i]);
        lungime[i] = 1;
        predecesor[i] = 0;

        for(int j = i - 1; j >= 1; --j){
            if(v[j] < v[i] && lungime[j] + 1 > lungime[i]){
                lungime[i] = lungime[j] + 1;
                predecesor[i] = j;
            }
        }

        if(lungime[i] > lungime[poz])
            poz = i;
    }

    fprintf(fout, "%d\n", lungime[poz]);
    refa(poz, fout);

    return 0;
}

void refa(int p, FILE *f){
    if(p == 0)
        return;
    refa(predecesor[p], f);
    fprintf(f, "%d ", v[p]);
}