十行求解 $O(n \log n)$ 求最长上升子序列

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
int n, x, f[100001];
int main() {
memset(f, 63, sizeof(f));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &x), *std::lower_bound(f + 1, f + n + 1, x) = x;
printf("%d\n", std::lower_bound(f + 1, f + n + 1, f[0]) - f - 1);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×