Pagini recente » Cod sursa (job #552798) | Cod sursa (job #891824) | Cod sursa (job #1305048) | Cod sursa (job #1925808) | Cod sursa (job #2674218)
//
// main.cpp
// scmax
//
// Created by Toie Vlad on 18/11/2020.
//
#include <iostream>
#include <vector>
#include <fstream>
#define MAX_N 100005
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, v[MAX_N], best[MAX_N], p[MAX_N], maxim, k, L[MAX_N], nr;
void afis(int i) {
if(p[i] > 0) {
afis(p[i]);
}
fout<<v[i]<<" ";
}
int cautBin(int x) {
int l, r, m;
l = 0;
r = nr;
m = (l+r)/2;
while (l <= r)
{
if (v[L[m]] < x && v[L[m+1]] >= x)
return m;
else if (v[L[m+1]] < x) {
l = m + 1;
m = (l + r)/2;
}
else {
r = m - 1;
m = (l + r)/2;
}
}
return nr;
}
int main()
{
int i, poz;
nr = 1;
fin>>n;
for (i = 1; i <= n; i++) {
fin>>v[i];
}
L[0] = 0;
best[1] = L[1] = 1;
for (i = 2; i <= n; i++)
{
poz = cautBin(v[i]);
p[i] = L[poz];
best[i] = poz + 1;
L[poz + 1] = i;
if (nr < poz + 1)
nr = poz + 1;
}
maxim = 0;
poz = 0;
for (i = 1; i <= n; i++) {
if (maxim < best[i]) {
maxim = best[i];
poz = i;
}
}
fout<<maxim<<endl;
afis(poz);
fout<<endl;
return 0;
}