Pagini recente » Cod sursa (job #2815442) | Cod sursa (job #112126) | Cod sursa (job #2880172) | Cod sursa (job #959313) | Cod sursa (job #628509)
Cod sursa(job #628509)
#include <fstream>
using namespace std;
const int MAX_N = 100005;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n;
int v[MAX_N];
int d[MAX_N];
void read() {
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i];
}
void write_solution(int pos) {
if (pos == 0) return;
for (int i = 0; i < pos; ++i)
if (v[i] < v[pos] && d[i] == d[pos] - 1) {
write_solution(i);
fout << v[pos] << " ";
return;
}
}
void solve() {
for (int i = 1; i <= n; ++i) {
d[i] = 1;
for (int j = 1; j < i; ++j)
if (v[j] < v[i] && d[j] + 1 > d[i])
d[i] = d[j] + 1;
}
// find max length
int best = 0, pos = -1;
for (int i = 1; i <= n; ++i)
if (d[i] > best) {
best = d[i];
pos = i;
}
fout << best << "\n";
write_solution(pos);
}
int main() {
read();
solve();
}