Pagini recente » Cod sursa (job #1793242) | Cod sursa (job #819573) | Cod sursa (job #280437) | Cod sursa (job #816593) | Cod sursa (job #2321989)
#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;
}