n²谁都会打，不说了。
这里讨论一下nlogn算法(单调不减)：
首先开始考虑单调性，我习惯性的以为是单调队列/栈优化的那个套路，想要找到一个跟下标有关的单调性却发现没有。
例如：我想过当下标增加时f[i]增加，后来发现了反例：1 3 4 2
事实上也没有别的想得到的了。
我跑去看题解，发现单调性是这个毒瘤：
当单调不减子序列长度增加时，每个长度对应的最小高度增加。
然后每次二分出一个长度，保证最小高度刚好不大于a[i]
然后用a[i]更新f[i]的最小高度...
然后就没啥难点了，A了。
#include <cstdio>
#include <algorithm>
#include <cstring> const int N = ; int a[N], f[N], p[N], top; inline int BS(int x) {
int l = , r = top, mid;
while(l < r) {
mid = (l + r + ) >> ;
if(p[mid] < x) {
r = mid - ;
}
else {
l = mid;
}
}
return r;
} inline int BS2(int x) {
int l = , r = top, mid;
while(l < r) {
mid = (l + r + ) >> ;
if(p[mid] >= x) {
r = mid - ;
}
else {
l = mid;
}
}
return r;
} int main() {
int n = , x;
while(scanf("%d", &x) != -) {
a[++n] = x;
}
for(int i = ; i <= n; i++) {
int t = BS(a[i]);
f[i] = t + ;
p[f[i]] = std::max(p[f[i]], a[i]);
top = std::max(top, f[i]);
}
printf("%d \n", top);
top = ;
memset(p, 0x7f, sizeof(p));
for(int i = ; i <= n; i++) {
int t = BS2(a[i]);
f[i] = t + ;
p[f[i]] = std::min(p[f[i]], a[i]);
top = std::max(top, f[i]);
}
printf("%d", top);
return ;
}
AC代码
附一张提交记录