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: $L_i$ 和 $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[t] = \max_{0 \le k < t} dp[k] + 1$$

如果 $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	不相交线段集问题