You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
47 lines
1.0 KiB
47 lines
1.0 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
const int N = 110;
|
|
int n; // 楼房的个数
|
|
int a[N]; // 楼房的高度数组
|
|
|
|
// 数组模拟栈
|
|
int f[N], fl;
|
|
int g[N], gl;
|
|
int res;
|
|
|
|
int main() {
|
|
int T;
|
|
cin >> T;
|
|
while (T--) {
|
|
// 保持好习惯，多组测试数据，记得每次清空结果数组
|
|
memset(f, 0, sizeof f);
|
|
memset(g, 0, sizeof g);
|
|
fl = 0, gl = 0;
|
|
|
|
cin >> n;
|
|
for (int i = 1; i <= n; i++) cin >> a[i];
|
|
|
|
// 正着求
|
|
for (int i = 1; i <= n; i++) {
|
|
if (a[i] > f[fl])
|
|
f[++fl] = a[i];
|
|
else
|
|
*lower_bound(f + 1, f + 1 + fl, a[i]) = a[i];
|
|
}
|
|
|
|
// 反着求
|
|
for (int i = n; i; i--) {
|
|
if (a[i] > g[gl])
|
|
g[++gl] = a[i];
|
|
else
|
|
*lower_bound(g + 1, g + 1 + gl, a[i]) = a[i];
|
|
}
|
|
// pk的最大结果
|
|
res = max(fl, gl);
|
|
// 输出
|
|
printf("%d\n", res);
|
|
}
|
|
return 0;
|
|
} |