25.11.20 最长不升序列LNIS和最长升序列LIS

LNIS
1.处理一个数时：
如果这个数小于等于当前序列的最后一个数，则直接接在后面，ct++
反之，从序列头开始寻找第一个比这个数小的数并且替代他，目的：使这个序列更容易接后面的数
2.代码模板
int LNIS(vector& a) {
vector tail;
for (int x : a) {
if (tail.empty() || x <= tail.back()) {
tail.push_back(x);
} else {
int l = 0, r = tail.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (tail[mid] < x) r = mid; // 找第一个 < x 的位置
else l = mid + 1;
}
tail[l] = x;
}
}
return tail.size();
}
LIS
逻辑与上面相同，唯一区别在比较和替换时的比较符号相反