Pagini recente » Cod sursa (job #2488345) | Cod sursa (job #2986925) | Cod sursa (job #2319780) | Cod sursa (job #1871427) | Cod sursa (job #1898932)
#include <fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
const int NM = 110;
const int inf = 2e9 + 10;
int N, i;
int v[NM], best[NM], prv[NM];
int get_pos(int n) {
int res = 0;
int left = 1; int right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
if (v[best[mid]] < v[n])
res = mid, left = mid + 1;
else right = mid - 1;
}
return res;
}
void print_lis(int n) {
if (n == 0) return;
print_lis(prv[n]);
out << v[n] << ' ';
}
int main()
{
in >> N;
for (i = 1; i <= N; ++i) {
in >> v[i];
}
v[0] = inf;
for (i = 1; i <= N; ++i) {
int current = get_pos(i);
best[current + 1] = i;
prv[i] = best[current];
}
int ans;
for (ans = 1; best[ans+1]; ++ans);
out << ans << '\n';
print_lis(best[ans]);
return 0;
}