Cod sursa(job #2321989)

Utilizator mariusgrafuMarius Grafu mariusgrafu Data 16 ianuarie 2019 22:07:19
Problema Subsir crescator maximal Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

void printParents (vector<int> v, vector<int> parents, int current) {
    if(parents[current] != -1) printParents(v, parents, parents[current]);
    out << v[current] << " ";
}

void scmax (vector<int> v) {
    vector<int> d(v.size(), 1);
    d[0] = 1;
    vector<int> parents(v.size(), -1);

    for(int i = 1; i < v.size(); ++i) {
        int dmax = 0;
        int parent = -1;
        for(int j = 0; j < i; ++j) {
            if(v[i] > v[j] && d[j] > dmax){
                    dmax = d[j];
                    parent = j;
            }
        }
        d[i] = 1 + dmax;
        parents[i] = parent;
    }

    int dmaxIdx = 0;
    for(int i = 1; i < d.size(); ++i) {
        if(d[i] > d[dmaxIdx]) dmaxIdx = i;
    }

    out << d[dmaxIdx] << "\n";
    printParents(v, parents, dmaxIdx);
}

int main()
{
    int n;
    in >> n;
    vector<int> v(n);

    for(int i = 0; i < n; ++i) {
        in >> v[i];
    }

    scmax(v);

    return 0;
}