Sunforger·4 months ago

问题描述

给定一个给定一个长度为 $$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