Cod sursa(job #1674937)

Utilizator preda.andreiPreda Andrei preda.andrei Data 4 aprilie 2016 22:58:39
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 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;

        if(v[poz] < v[i]){
            lungime[i] = lungime[poz] + 1;
            predecesor[i] = poz;
            poz = i;
        }
        else{
            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]);
}