問題描述#
給定一個給定一個長度為 的整數序列 ，求其中一個子序列（不要求連續），使得其元素嚴格遞增，且長度最長。有時還要求恢復出這個最長子序列。
案例：
A = [10, 9, 2, 5, 3, 7, 101, 18]
LIS = [2, 3, 7, 101] # 長度為 4
應用場景#
生物信息學中對 DNA 序列結構的分析
股票分析中尋找上漲趨勢
機器人路徑規劃中的序列最優控制
解法一： 動態規劃#
思路： 定義 為以第 個元素結尾的最長上升子序列的長度，初始值均為 1
狀態轉移方程：
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)
時間複雜度：
空間複雜度：
可以返回 LIS 序列
解法二：貪心 + 二分查找#
思路：維護一個數組 tail，表示所有長度為 k 的上升子序列中，最小那個序列的結尾元素。
對於每個數 x，我們在 tail 中查找第一個 大於等於 x 的位置 i
如果找到了，就用 x 替換 （貪心，因為更小的結尾更可能擴展出更長的上升子序列）
如果沒找到（說明 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