最长上升子序列 II

题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤100000，
−10⁹≤数列中的数≤10⁹

输入样例

7
3 1 2 1 8 5 6
1
2

输出样例

4
1

思路

在AcWing的题解区再现妙手，原题解链接为在此。
大体的思路是这样的，使用vector模拟堆栈，这个堆栈的长度维护的便是最长上升子序列的长度。首先将序列的第一个数存入栈，从第二个数开始遍历序列。

• 如果第i个数大于栈顶元素，那么这个数也需要入栈（显然，入栈的元素大于之前的栈顶元素，栈内保持升序）。这个数入栈之后，使栈的规模提升了，即提高了最长上升子序列的规模，对答案产生了直接贡献；
• 否则（即，第i个数小于等于栈顶元素），使用lower_bound函数（模拟的是二分，寻找的是目标可迭代对象中第一个大于等于目标值<此处的目标值便是这个第i个数>的数的位置指针，加*可以解除指针使其退化为引用）在堆栈中找到第一个大于等于第i个数的数，将堆栈中的这个数替换为第i个数。值得注意的是，替换的数可能在当前的栈顶，也可能在堆栈中间的某个位置，如果在堆栈中间的某个位置的话（甚至可能是栈底，即v[0]