题目链接
思路
$$ \begin{aligned}经典的最长非降子序列问题\end{aligned} $$
时间复杂度
$$ O(Nlog(N)) $$
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 4e4 + 10;
int a[MAXN];
int main() {
int T;
scanf("%d", &T);// don't forget &
while (T--) {
int n;
scanf("%d", &n);// don't forget &
memset(a, 0x3f, sizeof a);
int ans = 0;
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);// don't forget &
int l = 1, r = n, cur = l;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[mid] > x) {
cur = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
a[cur] = x;
ans = max(ans, cur);
}
printf("%d\n", ans);
}
return 0;
}