LIS最長遞增子序列

01為什麼需要它

看到這些關鍵字就想到它：子序列（可以不連續）、一路遞增、最長鏈、一個套一個、兩個維度都要更大、最少刪除或搬動幾個才有序、n 到 10⁵ 需要 O(n log n)。

02核心概念

最長遞增子序列（LIS）：從陣列挑出若干元素，保持原本的先後順序且嚴格遞增，最多能挑幾個。子序列可以不連續，這是它和「最長連續遞增子陣列」的差別，後者掃一遍就好。直覺的狀態是 dp[i] = 以 nums[i] 結尾的 LIS 長度。一定要「以它結尾」，因為要把 nums[i] 接到某條子序列後面，得知道那條子序列的最後一個值比它小。轉移式是 dp[i] = 1 + max(dp[j])，其中 j < i 且 nums[j] < nums[i]，找不到這樣的 j 就是 1。LIS 可能在任何位置結束，所以答案是 max(dp)，不是最後一格。

tails 版本換一個狀態：tails[k] = 所有長度為 k+1 的遞增子序列中最小的結尾值。同樣長度的子序列，結尾越小，之後越容易接上新元素，所以每個長度只要記最好的那一個。關鍵不變量是 tails 嚴格遞增：若 tails[k] ≥ tails[k+1]，取結尾為 tails[k+1] 的那條長度 k+2 子序列，它的第 k+1 個元素比 tails[k+1] 小，也就比 tails[k] 小，和「tails[k] 是最小結尾」矛盾。既然有序，處理新元素 x 時用 lower_bound 找第一個 ≥ x 的位置 pos：tails[pos-1] < x，x 能接在長度 pos 的子序列後面，形成長度 pos+1、結尾是 x 的子序列；又因為 x ≤ tails[pos]，把 tails[pos] 換成 x 只會更好，其他格都不受影響。pos 等於 tails 長度時就 append，LIS 變長一格。這個做法也叫耐心排序（patience sorting），tails 的每一格就是一疊牌最上面那張。

複雜度：O(n²) 版本不論資料長怎樣，內層迴圈都要把前面看完，最好、最壞都是 Θ(n²)，空間 O(n)。tails 版本每個元素做一次二分搜尋，tails 的長度最多是 LIS 長度 L，所以是 O(n log L)：完全遞減的資料 L = 1，接近 O(n)；完全遞增時 L = n，就是最壞的 O(n log n)。空間是 tails 的 O(L)，要還原序列再加一個 O(n) 的 parent 陣列，合計 O(n)。n = 10⁵ 時 n² 是 10¹⁰，只有 n log n（約 1.7 × 10⁶）跑得動。

常見的坑：tails 不是 LIS 本身，它的每一格可能來自不同的子序列，只有長度是對的，要序列就改存索引並記下每個元素接在誰後面。嚴格或非嚴格：嚴格遞增用 lower_bound（bisect_left），允許相等的非遞減用 upper_bound（bisect_right），用錯時重複元素會被多算或少算。二維要先排序，第一維相同時第二維遞減，否則同寬的信封會被當成能互套。要計數（有幾條 LIS）時 tails 做不到，得回到 O(n²) DP 另外記 count[i]。和相鄰課程比：1-D DP 的狀態只依賴前一兩項，LIS 的 dp[i] 依賴前面所有項，才會是 O(n²)；LCS 是兩個序列的 O(mn) 二維表，LIS 其實等於「nums 和排序去重後的 nums 的 LCS」，反過來當其中一個序列元素互不重複時，LCS 也能轉成 LIS 做到 O(n log n)。

03演算法步驟

1. 1確認要的是子序列（可跳過）還是連續子陣列、嚴格遞增還是允許相等。若是二維（信封、箱子），先依第一維遞增、同值時第二維遞減排序，只留第二維。
2. 2n 在幾千以內或需要計數：dp = [1] * n，對每個 i 掃所有 j < i，nums[j] < nums[i] 時 dp[i] = max(dp[i], dp[j] + 1)，答案取 max(dp)。
3. 3要 O(n log n)：開一個空的 tails，對每個 x 求 pos = lower_bound(tails, x)（非遞減改用 upper_bound）。
4. 4pos == len(tails) 就 append，否則 tails[pos] = x。全部處理完，len(tails) 就是 LIS 長度。
5. 5需要序列本身：tails 改存索引，處理第 i 個元素時記 parent[i] = tails[pos-1]（pos 為 0 時是 −1），最後從 tails 的最後一格沿 parent 往回走，再反轉。

04互動示範

八天的股價 [3, 1, 4, 1, 5, 9, 2, 6]，兩個模式跑同一份資料。「O(n²) DP 表」逐格填 dp[i]：藍色是目前的 i，綠色是比它小、可以接在後面的 j，黃色是其中 dp 最大的那個；注意 i = 3 的 1 接不到前面的 1，因為要嚴格遞增。最後一步用綠色標出沿前驅回溯得到的 3 → 4 → 5 → 9。「O(n log n) tails」每個元素先二分搜尋（黃色是找到的位置，黃色虛線 + 代表接在尾端），再取代或 append（藍色）。看最後一步：tails 是 [1, 2, 5, 6]，長度 4 是對的，但「來自」的索引 3、6、4、7 並不遞增，它不是一條真正的子序列。

05程式碼

四個函式：O(n²) DP（Python 版順便用 prev 還原序列，C++ 版只回傳長度）、只求長度的 tails 版、存索引加 parent 還原序列的 O(n log n) 版，以及用排序把俄羅斯套娃信封降成一維 LIS。兩種做法都放，是因為 O(n²) 版好理解、能延伸到計數，tails 版才應付得了大資料。範例用的就是互動示範的八天股價，兩個版本還原出的 LIS 不同但一樣長。

from bisect import bisect_left


def lis_dp(nums):
    """O(n²)：dp[i] = 以 nums[i] 結尾的 LIS 長度，順便還原一條 LIS"""
    n = len(nums)
    if n == 0:
        return []
    dp = [1] * n
    prev = [-1] * n                          # prev[i]：nums[i] 接在哪個索引後面
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    k = max(range(n), key=dp.__getitem__)    # 答案是 dp 的最大值，不一定是 dp[-1]
    seq = []
    while k != -1:
        seq.append(nums[k])
        k = prev[k]
    return seq[::-1]


def lis_length(nums):
    """O(n log n)：tails[k] = 長度 k+1 的遞增子序列中最小的結尾"""
    tails = []
    for x in nums:
        pos = bisect_left(tails, x)          # 第一個 >= x；非遞減改用 bisect_right
        if pos == len(tails):
            tails.append(x)                  # 比所有結尾都大：LIS 變長
        else:
            tails[pos] = x                   # 同樣長度，結尾換成更小的
    return len(tails)


def lis_sequence(nums):
    """O(n log n) 並還原序列：tails 改存索引，另記每個元素的前驅"""
    tails = []                               # tails[k]：長度 k+1 的最小結尾在 nums 的索引
    parent = [-1] * len(nums)
    for i, x in enumerate(nums):
        pos = bisect_left(tails, x, key=lambda t: nums[t])  # key 參數需 Python 3.10+
        if pos > 0:
            parent[i] = tails[pos - 1]       # 接在長度 pos 的最小結尾後面
        if pos == len(tails):
            tails.append(i)
        else:
            tails[pos] = i
    seq, k = [], tails[-1] if tails else -1
    while k != -1:
        seq.append(nums[k])
        k = parent[k]
    return seq[::-1]


def max_envelopes(envelopes):
    """俄羅斯套娃信封：寬遞增、同寬時高遞減，再對高求 LIS"""
    order = sorted(envelopes, key=lambda e: (e[0], -e[1]))
    return lis_length([h for _, h in order])


if __name__ == "__main__":
    prices = [3, 1, 4, 1, 5, 9, 2, 6]
    print(lis_dp(prices))          # [3, 4, 5, 9]
    print(lis_length(prices))      # 4
    print(lis_sequence(prices))    # [1, 4, 5, 6]（另一條同樣長的 LIS）
    print(max_envelopes([[5, 4], [6, 4], [6, 7], [2, 3]]))  # 3
    shelf = [4, 2, 5, 1, 3, 6]     # 書架上的索書號
    print(len(shelf) - lis_length(shelf))  # 3（最少搬 3 本）

06練習題

• LeetCode 300Longest Increasing Subsequence（兩種做法都寫一次）Medium
• LeetCode 334Increasing Triplet Subsequence（長度只到 3 的 tails）Medium
• LeetCode 673Number of Longest Increasing Subsequence（O(n²) DP 加計數）Medium
• LeetCode 354Russian Doll Envelopes（排序降成一維）Hard
• LeetCode 1964Find the Longest Valid Obstacle Course at Each Position（非遞減用 upper_bound）Hard
• LeetCode 1713Minimum Operations to Make a Subsequence（LCS 轉 LIS）Hard