LIS 指的是最长递增子序列（Longest Increasing Subsequence）问题，可以以 $\mathrm O(n\log n)$ 实现。

这个问题和 lcs 问题之间具有一些相关性，对于一些特殊的 lcs 问题，可以退化成 lis 进行解决。

我们对于一个序列 nums = [2, 6, 8, 3, 4, 5, 1] 考虑，维护一个递增子序列 sub1 = []：

  1. 第一个元素 2，直接插入序列中，sub1 = [2]。
  2. 第二个元素 6，发现可以接在 sub1 中，sub1 = [2, 6]。
  3. 第三个元素 8，继续接在 sub1 中，sub1 = [2, 6, 8]。
  4. 第四个元素 3，注意到无法继续延续 sub1 ，但是注意到可以形成子序列 [2, 3]，因此建立 sub2 = [2, 3]。
  5. 第五个元素 4，无法延续 sub1，但可以延续 sub2 = [2, 3, 4]。
  6. 第六个元素 5，继续延续 sub2 = [2, 3, 4, 5]。
  7. 第七个元素 1，sub1, sub2 都无法延续，建立 sub3 = [1]。 最终选择最长的序列作为答案 ans = len(sub2) = 4。

如果每次无法延长任何序列都新建一个序列的话，空间复杂度和时间复杂度都很大。假设我们不需要保存子序列的具体内容，而只需要长度的话，我们完全可以考虑将之前的元素覆盖掉。

具体来说，考虑第四个元素 3 插入的过程：我们发现 3 可以放在 2 后面，但不能放在 6 后面，因此直接将 6 替换成 3，sub1 = [2, 3, 8]。注意我们需要把 6 删掉，而不能把 6 挪到后面。因为 6 只能形成长度为 2 的子序列。

这样我们每次拿到一个新元素 num 时，只需要找到能插入的位置 i 使得：$\text{sub[i-1]} < \text{num} \le \text{sub[i]}$ 就行了。可以用 二分搜索实现，复杂度 $\mathrm O(\log n)$。

代码 Link to heading

二分部分可以参考 bisect 算法

 1class Solution:
 2    def lengthOfLIS(self, nums: List[int]) -> int:
 3        d = []
 4        for n in nums:
 5            if not d or n > d[-1]:
 6                d.append(n)
 7            else:
 8                l, r = 0, len(d)
 9                while l < r:
10                    mid = (l + r) // 2
11                    if d[mid] >= n:
12                        r = mid
13                    else:
14                        l = mid + 1
15                d[l] = n
16        return len(d)