Pagini recente » Cod sursa (job #1498657) | Cod sursa (job #1161156) | Cod sursa (job #1525100) | Cod sursa (job #206523) | Cod sursa (job #2890125)
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int n; cin >> n;
int v[n + 1] = {0};
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
int lis_max_index = 1;
int next[n + 1] = {0};
int lis[n + 1] = {0};
lis[n] = 1;
next[n] = n;
for (int i = n - 1; i >= 1; --i) {
int max_index = i;
for (int j = i + 1; j <= n; j++) {
if (lis[j] > lis[max_index] and v[j] > v[i]) {
max_index = j;
}
}
lis[i] = lis[max_index] + 1;
next[i] = max_index;
if (lis[i] > lis[lis_max_index]) {
lis_max_index = i;
}
}
cout << lis[lis_max_index] << endl;
int i = lis_max_index;
while (i != next[i]) {
cout << v[i] << " ";
i = next[i];
}
cout << v[i] << endl;
return 0;
}