算法：最长上升子序列问题

问题描述#

给定一个给定一个长度为 $n$ 的整数序列 $A=[a_1, ..., a_n]$ ，求其中一个子序列（不要求连续），使得其元素严格递增，且长度最长。有时还要求恢复出这个最长子序列。

案例：

A = [10, 9, 2, 5, 3, 7, 101, 18]
LIS = [2, 3, 7, 101]  # 长度为 4

应用场景#

生物信息学中对 DNA 序列结构的分析
股票分析中寻找上涨趋势
机器人路径规划中的序列最优控制

解法一：动态规划#

思路：定义 $dp[i]$ 为以第 $i$ 个元素结尾的最长上升子序列的长度，初始值均为 1
状态转移方程： $dp[i] = max(dp[j] + 1) \quad \forall j < i ~~\& ~~A[j] < A[i]$

def LIS_DP(A):
    n = len(A)
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if A[j] < A[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

可以返回 LIS 序列

解法二：贪心 + 二分查找#

思路：维护一个数组 tail，表示所有长度为 k 的上升子序列中，最小那个序列的结尾元素。
对于每个数 x，我们在 tail 中查找第一个大于等于 x 的位置 i
如果找到了，就用 x 替换 $tail[i]$ （贪心，因为更小的结尾更可能扩展出更长的上升子序列）
如果没找到（说明 x 比所有的都大），就把 x 追加到 tail 末尾
最终，len (tail) 就是最长上升子序列的长度。

案例说明

A = [10, 9, 2, 5, 3, 7, 101, 18]

tail = []

# tail 的变化
10    → [10]
9     → [9]
2     → [2]
5     → [2, 5]
3     → [2, 3]
7     → [2, 3, 7]
101   → [2, 3, 7, 101]
18    → [2, 3, 7, 18]

# 结论 LIS 长度为 4

伪代码：

import bisect

def LIS_binary_search(A):
    tail = []
    for x in A:
        i = bisect.bisect_left(tail, x)
        if i == len(tail):
            tail.append(x)
        else:
            tail[i] = x
    return len(tail)

为什么不能直接用 tail 得到 LIS 序列？

因为 tail 不是 LIS 本身，它是 “多个潜在 LIS 的贪心压缩”，它不断被覆盖和替换，并不保留完整路径。

举个例子：

A = [3, 10, 2, 1, 20]
# tail 可能为：[1, 10, 20]
# 但 LIS 是 [3, 10, 20]

用 DP + 回溯，恢复 LIS 序列#

思路：为了输出 LIS 本身，我们需要额外记录 “每个位置的前驱”。

dp [i]: 表示以 A [i] 结尾的最长 LIS 长度
pre [i]: 表示在 A [i] 前一个元素的索引（用于回溯路径）
遍历每个位置 i，找所有 j <i 且 A [j] < A [i] 的 dp [j]，然后：
若 dp [j] + 1 > dp [i]，则更新 dp [i] = dp [j] + 1，并设 pre [i] = j

def get_LIS_sequence(A):
    n = len(A)
    dp = [1] * n
    pre = [-1] * n  # 用于回溯路径

    max_len = 1
    last_index = 0

    for i in range(n):
        for j in range(i):
            if A[j] < A[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                pre[i] = j

        if dp[i] > max_len:
            max_len = dp[i]
            last_index = i

    # 回溯路径
    lis = []
    i = last_index
    while i != -1:
        lis.append(A[i])
        i = pre[i]

    lis.reverse()
    return lis

练习题#

洛谷 B3637 最长上升子序列