最长上升子序列问题【LIS】
willow_Catkin
·
·
个人记录
对于给定序列A，要求最长子序列M，使得M中的元素单调递增
常规做法时间复杂度为O(n^{2})，较简单，不多赘述。
这里记录的是本问题的贪心解，时间复杂度O(nlogn)
我们引入序列q
贪心思路：较小的数开头的数作为的子序列 比 较大的数作为开头的子序列 更好
贪心步骤：
1. 开一个数组q[i]，存的是以长度为i的上升子序列中末尾元素最小的数
2. q[]一开始是空集，长度为0
3. 遍历每个数x，对于当前数x, 先找到一个最大的小于x的数c：
- 情况1：若找不到c, 扩大q[]的长度并记录当前数x
- 情况2：若找到c, 就存在一个不等式c < x ≤ a < b, 则将x覆盖a的位置
```cpp
int tt = 0;
q[0] = -1;
for(int i = 1; i <= n; i ++){
int l = 0, r = tt;
while (l < r){
int mid = l + r + 1 >> 1;
if(a[i] > q[mid]) l = mid;
else r = mid - 1;
}
q[r + 1] = a[i];
tt = max(tt, r + 1);
}
```