Pagini recente » Cod sursa (job #2386698) | Cod sursa (job #2806007) | Cod sursa (job #2911064) | Cod sursa (job #1184310) | Cod sursa (job #2777010)
#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
#define dim 100001
ifstream in("scmax.in");
ofstream out("scmax.out");
int v[dim], bst[dim], back[dim];
void scmax(int pos) {
if (back[pos] == -1) {
out << v[pos] << " ";
return;
}
scmax(back[pos]);
out << v[pos] << " ";
}
int main()
{
int n, i, lmax,pos_f;
in >> n;
for(i = 1; i <= n; i++) {
in >> v[i];
}
bst[1] = 1;
back[1] = -1;
lmax = 1;
pos_f = 1;
for(i = 2; i <= n; i++) {
bst[i] = 1;
back[i] = -1;
for(int j = 1; j < i; j++)
{
if(bst[i] < bst[j]+1 && v[j]<v[i]) {
bst[i] = bst[j] + 1;
back[i] = j;
if (bst[i] > lmax) {
lmax = bst[i];
pos_f = i;
}
}
}
}
// int pos = pos_f;
// while(back[pos] != -1) {
// out << v[pos] << " ";
// pos = back[pos];
// }
// out << v[pos] << "\n";
out << lmax << '\n';
scmax(pos_f);
return 0;
}