Cod sursa(job #2419824)

Utilizator ana_are_mere1997Ana Secuiu ana_are_mere1997 Data 9 mai 2019 15:23:41
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>

#define N_max 100000

int v[N_max];
int prec[N_max];

int N;
int last_poz;

void read_input()
{
    std::ifstream f_in ("scmax.in");

    f_in >> N;
    for (int i = 0; i < N; i++) {
        f_in >> v[i];
        prec[i] = -1;
    }
}

int compute_max_len()
{
    std::vector<int> dp(N);
    int max;

    dp[0] = 1;
    max = dp[0];

    for (int i = 1; i < N; i++) {
        dp[i] = 1;

        for (int j = 0; j < i; j++) {
            if (v[i] > v[j]) {
                if (dp[j] + 1 > dp[i] && dp[j] + 1 > max) {
                    /* for max_len computation */
                    dp[i] = dp[j] + 1;
                    max = dp[i];

                    /* for reconstruction */
                    last_poz = i;
                    prec[i] = j;
                }
            }
        }
    }
    return max;

}

void reconstruct(int max_len, std::ofstream &f_out)
{

    int previous = 0, i = 0;
    int succession[max_len];

    succession[i++] = v[last_poz];

    while (previous != -1) {
        previous = prec[last_poz];
        succession[i++] = v[previous];
        last_poz = previous;
    }
    for (i = max_len - 1; i >= 0; i--)
        f_out << succession[i] << " ";
    f_out << std::endl;
}

void print_output(int max_len)
{
    std::ofstream f_out ("scmax.out");

    f_out << max_len << std::endl;

    reconstruct(max_len, f_out);
}
int main() {

    int max_len;

    read_input();
    max_len = compute_max_len();

    print_output(max_len);
    return 0;
}