04_Longest Increasing Subsequence 最长递增子序列
最长递增子序列
Authors: Michael Cao, Benjamin Qi, Andi Qu, Andrew Wang
Contributors: Dong Liu, Siyong Huang, Aryansh Shrivastava, Kevin Sheng, Katja Frantzen
先决条件
- Gold - Introduction to DP (动态规划简介)
教程
令 $A$ 为我们要寻找最长递增子序列（LIS）的数组。
慢速解法
时间复杂度: $O(N^2)$
令 $dp[i]$ 表示以 $A[i]$ 结尾的最长递增子序列的长度。我们可以通过简单的方法在 $O(N^2)$ 时间内计算 $dp$（从而得到 LIS）：
from typing import List
def find_lis(a: List[int]) -> int:
lis = 0
dp = [1] * len(a)
for i in range(len(a)):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j] + 1)
lis = max(lis, dp[i])
return lis然而，我们可以做得更好！
快速解法
时间复杂度: $O(N \log N)$
令 $L_i$ 是一个数组（0 索引），其中 $L_i[j]$ 是从 $A$ 的前 $i$ 个元素中最小的一个元素，它以长度为 $j+1$ 的递增序列结束（如果没有这样的元素则为 $\infty$）。
引理 1: $L_i$ 形成一个严格递增的序列。
引理 2: 以 $A[i+1]$ 结尾的最长递增子序列的长度等于满足 $L_i[j] \ge A[i+1]$ 的最小索引 $j$。
引理 3: $Li$ 和 $L{i+1}$ 之间最多有 1 个元素不同。
要在 $O(\log N)$ 时间内找到并更新描述的 $j$，我们可以使用带二分查找的列表：
from typing import List
from bisect import bisect_left
def find_lis(arr: List[int]) -> int:
min_endings = []
for i in arr:
pos = bisect_left(min_endings, i)
if pos == len(min_endings): # we can have a new, longer increasing subsequence!
min_endings.append(i)
else: # oh ok, at least we can make the ending element smaller
min_endings[pos] = i
return len(min_endings)RMQ 数据结构解法
时间复杂度: $O(N \log N)$，但可能比之前的解决方案慢一个常数因子。
设 $dp[k]$ 为以元素 $k \in a$ 结尾的 $a$ 的 LIS 长度。我们的基本情况是 $dp[a[0]] = 1$。由于 LIS 具有最优子结构特性，我们按以下方式进行转换：
如果 $dp$ 是一个 RMQ 数据结构，$dp[t]$ 的变化只是一个点更新，而 $\max_{0 \le k < t} dp[k]$ 的计算是一个区间查询。
应用 1 - 不相交的线段
首先，如果两个线段 $(l_1, r_1)$ 和 $(l_2, r_2)$ 相交（假设 $l_1 < l_2$），我们可以注意到 $l_1 < l_2 \implies r_1 > r_2$。
这意味着一组不相交的线段对于所有对 $(i, j)$ 都满足 $l_i < l_j \implies r_i < r_j$！
设 $A$ 是一个数组，其中 $A[i] = x$ 表示位于位置 $i$ 的右端点的线段的左端点位于位置 $x$。
如果我们被要求找出不相交线段集的最大大小，答案将是 $A$ 的最长递增子序列！
应用 2 - 最少递增子序列数
引理（简单）: 覆盖 $A$ 所需的最少递增子序列数至少等于 $A$ 最长非递增子序列的长度。
命题: 覆盖 $A$ 所需的最少递增子序列的数量等于 $A$ 最长非递增子序列的长度！
证明: 设 $f_i$ 表示以 $A_i$ 结尾的最长非递增子序列的长度。那么对于固定的 $t$，满足 $f_i = t$ 的 $A_i$ 对于每个 $t$ 都是一个递增子序列。所以我们用（最长非递增子序列的长度）个递增子序列覆盖了 $A$。
另一种证明: 这只是 Dilworth 定理的一个特例。
示例 - PCB
Focus Problem: 在继续之前，请尽力解决这个问题！
这个问题要求我们找到最小数量的不交线段集。
from bisect import bisect_left
n = int(input())
board = []
endpoints = []
for _ in range(n):
l, r = map(int, input().split())
board.append((l, r))
board.sort()
endpoints.append(board[0][1])
for x in range(1, n):
v = board[x][1]
if v < endpoints[-1]:
endpoints.append(v)
else:
index = bisect_left(
[-x for x in endpoints], -v
) # invert list in order to use bisect_left
endpoints[index] = v
print(len(endpoints))总结
| 解法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 暴力 DP | $O(N^2)$ | $O(N)$ |
| 二分查找优化 | $O(N \log N)$ | $O(N)$ |
| RMQ/线段树 | $O(N \log N)$ | $O(N)$ |
经典问题
| 题目 | 难度 | 描述 |
|---|---|---|
| Increasing Subsequence | Easy | 计算最长递增子序列长度 |
| PCB | Hard | 不相交线段集问题 |