Cod sursa(job #2637985)

Utilizator alex.livadaruLivadaru Alexandru alex.livadaru Data 26 iulie 2020 11:52:30
Problema Subsir crescator maximal Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

void sequence(int imax, vector<int> arr,
vector<int> next) {
    if (imax != -1) {
        sequence(next[imax], arr, next);
        fout << arr[imax] << " ";
    }
}

int main() {
    int N, imax, maxlen = 1;
    fin >> N;

    vector<int> arr(N);
    vector<int> len(N);
    vector<int> next(N, -1);

    for (int i = 0; i < N; ++i) {
        fin >> arr[i];
    }
    fin.close();

    len[0] = 1;

    for (int i = 1; i < N; ++i) {
        len[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (arr[i] > arr[j] && len[i] < len[j] + 1) {
                len[i] = len[j] + 1;
                next[i] = j;
            }
        }

        if (len[i] > maxlen) {
            maxlen = len[i];
            imax = i;
        }
    }

    fout << maxlen << "\n";
    sequence(imax, arr, next);

    fout.close();

    return 0;
}