🟡 300. Longest Increasing Subsequence

LIS 是研究所考試常見的題目，但參考書提供的考試寫法在實際使用上有一些限制，在這題直接使用會 WA 。在這裡以LeetCode 300. Longest Increasing Subsequence 為例，紀錄了時間複雜度從 $O(n^2)$ 到 $O(nlogn)$ 的三種解法，並在題目要求外，額外添加了還原 LIS 的過程。

由於題目要求的是 LIS 的長度，因此還原部分的程式碼未經完全測試，僅供參考。若有錯誤之處，還請斧正。

方法一：視為LCS問題後，Dynamic Programming (in Textbook)

這裡使用了在 CLRS Exercise 14.4-5 的 Solution 中給出的方法：

令 $X$ 為原序列， $Y$ 為原序列排序後所得的序列，
$X$ $X$ 和 $Y$ $Y$ 的 Longest Common Subsequence (LCS)，就是 $X$ $X$ 的 Longest Increasing Subsequence (LIS)。
- 這裡把 $X$ 擺在左邊， $Y$ 擺在上面，方便理解。
但直接使用這種方法，若遇到數字重複的的情況，就會出錯，因此要先對 $Y$ 去重。
紀錄LCS時，使用了兩個二維陣列， $dp$ $d p$ 表示 LCS 的長度， $label$ $l ab e l$ 表示 LCS 的轉移來源。
- 若 $X[i-1] == Y[j-1]$ ，則 $dp[i][j] = dp[i-1][j-1] + 1$ ，且 $label[i][j] = "↖"$ 。代表 $X[i-1]$ 和 $Y[j-1]$ 相等，可以接在 $X[:i-1]$ 和 $Y[:j-1]$ 的 LCS 的末尾。
- 若 $X[i-1] \neq Y[j-1]$ ，則 $dp[i][j] = max(dp[i-1][j], dp[i][j-1])$ ，且 $label[i][j] = "↑"$ 或 $label[i][j] = "←"$ 。代表不相等，則各退一步，取最大值。
在重購 LCS 時，從 dp 中找到最長的 LCS 長度，並依照 $label$ 的方向，找到轉移來源，即可重構出對應的 LCS。
時間複雜度： $O(n^2)$ ，其中排序的時間複雜度為 $O(nlogn)$ ，LCS 的時間複雜度為 $O(n^2)$ 。
空間複雜度： $O(n^2)$ ， $dp$ 和 $label$ 各佔一個 $n \times m$ 的二維陣列。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        Y = sorted(list(set(X))) # Y 為 X 排序後的序列，要去重
        n, m = len(X), len(Y)

        # 1. 用 dp 和 label 來紀錄 LCS
        dp = [[0] * (m+1) for _ in range(n+1)] # dp[i][j] 表示 X[:i] 和 Y[:j] 的 LCS 長度
        label = [[""] * (m+1) for _ in range(n+1)] # label[i][j] 表示 X[:i] 和 Y[:j] 的 LCS 的最後一個元素的方向
        for i in range(1, n+1):
            for j in range(1, m+1):
                if X[i-1] == Y[j-1]: # X[i-1] 和 Y[j-1] 相等，可以接在 X[:i-1] 和 Y[:j-1] 的 LCS 的末尾
                    dp[i][j] = dp[i-1][j-1] + 1 
                    label[i][j] = "↖"
                elif dp[i-1][j] >= dp[i][j-1]:
                    dp[i][j] = dp[i-1][j]
                    label[i][j] = "↑"
                else:
                    dp[i][j] = dp[i][j-1]
                    label[i][j] = "←"
        
        # 2. 從 dp 中找到最長的 LCS 長度，並從 label 中重構出對應的 LCS (由後往前)
        res = [-1] * dp[n][m] # LCS 長度為 dp[n][m]
        i, j = n, m
        while i > 0 and j > 0:
            if label[i][j] == "↖":
                res[dp[i][j]-1] = X[i-1]
                i -= 1
                j -= 1
            elif label[i][j] == "↑":
                i -= 1
            else:
                j -= 1
        print(res) # LIS
        return dp[n][m] # LIS 長度

方法二：直接做 Dynamic Programming

相對直覺，可以從「求 LIS 長度」直接想到的方法。

令 $dp[i]$ 表示以 $nums[i]$ 結尾的 LIS 長度；令 $prev[i]$ 表示以 $nums[i]$ 結尾的 LIS 的前一個位置。
則 $dp[i] = max(dp[i], dp[j] + 1)$ $d p [i] = ma x (d p [i], d p [j] + 1)$ for $j \in [0, i)$ $j \in [0, i)$ if $nums[j] < nums[i]$ $n u m s [j] < n u m s [i]$ 。
- 即枚舉所有位置 $i$ 以及 $i$ 前面的所有位置 $j$ ，若 $nums[j] < nums[i]$ ，則 $nums[i]$ 可以接在 $nums[j]$ 後面，並構成更長的 LIS ，更新 $dp[i]$ 和 $prev[i]$ 。
在重購 LIS 時，從 $dp$ 中找到最長的 LIS 長度，並從 $prev$ 中重構出對應的 LIS (由後往前)。
時間複雜度： $O(n^2)$
空間複雜度： $O(n)$ ， $dp$ 和 $prev$ 各佔一個長度為 $n$ 的陣列。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        # 1. 用 dp 和 prev 來紀錄 LIS
        prev = [-1] * n # prev[i] 表示以 nums[i] 結尾的 LIS 的前一個位置
        dp = [1] * n # dp[i] 表示以 nums[i] 結尾的 LIS 長度
        for i in range(1, n): # 枚舉所有位置 i
            for j in range(i): # 枚舉 i 前面的所有位置 j
                if nums[j] < nums[i]: # nums[i] 可以接在 nums[j] 後面
                    if dp[j] + 1 > dp[i]: # 若可以得到更大的LIS長度，更新 dp[i] 和 prev[i]
                        dp[i] = dp[j] + 1
                        prev[i] = j

        # 2. 從 dp 中找到最長的 LIS 長度，並從 prev 中重構出對應的 LIS (由後往前)
        max_len = max(dp)
        res = [-1] * max_len
        for i in range(n-1, -1, -1):
            if dp[i] == max_len:
                cur = i
                idx = max_len - 1
                while cur != -1:
                    res[idx] = nums[cur]
                    cur = prev[cur]
                    idx -= 1
                break
        print(res)
        return max_len

方法三：Greedy + Binary Search

CLRS Exercise 15.4-6⋆ 要求的 O(nlogn) 時間複雜度的演算法，即 Robinson-Schensted-Knuth Algorithm 。

如果已經得到的 LIS 結尾的數越小，那麼在後面接上其他數，會有更大的可能構成一個長度更長的 LIS。也就是說，在長度固定的情況下，結尾越小越好。根據這個貪心思路，可以記錄以下資訊：
- tail[i] 表示長度為 i+1 的 LIS 的最後一個元素的最小值，初始化 tail[0] = nums[0]
  - 需要注意的是， $tail$ 並不是LIS ，只是用來計算 LIS 長度的輔助陣列
- pos[i] 紀錄 nums[i] 在 LIS 中的第幾個位置
遍歷所有元素時，若 $nums[i] > tail[-1]$ ，則可以構成更長的 LIS，將其接在 $tail$ 的末尾，並更新 $pos[i]$ 。
否則，在 $tail$ 中二分查找，找到第一個大於等於 $nums[i]$ 的元素，並將其更新為 $nums[i]$ 。
重構時，從 $pos$ 中找到最後一個元素，並從後往前重構 LIS。
時間複雜度： $O(nlogn)$ ，遍歷 $n$ 個元素，每次二分查找的時間複雜度為 $O(logn)$ 。
空間複雜度： $O(n)$ ， $tail$ 和 $pos$ 各佔一個長度為 $n$ 的陣列。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)

        tail = [nums[0]] # tail[i] 表示 長度為 i+1 的 LIS 的最後一個元素的最小值，初始化 tail[0] = nums[0]
        pos = [0] * n # pos[i] 紀錄 nums[i] 在 LIS 中的第幾個位置

        for i in range(1, n):
            if nums[i] > tail[-1]: # nums[i] 可以接在 tail 的末尾，並構成更長的 LIS
                tail.append(nums[i]) # tail 長度加 1
                # 這裡可以直接跳過，因為 nums[i] > tail[-1]，所以二分查找的結果一定是新增的元素的位置
                # 但不加結果是相同的，只是多了一次不必要的二分查找
                pos[i] = len(tail) - 1
                continue

            # 在 tail 中二分查找，找到第一個大於等於 nums[i] 的元素，並將其更新為 nums[i]
            # left = bisect_left(tail, nums[i])
            left = 0
            right = len(tail) - 1
            while left <= right: # [left, right]
                mid = (left + right) // 2
                if tail[mid] < nums[i]:
                    left = mid + 1
                else:
                    right = mid -1
            tail[left] = nums[i]
            pos[i] = left

        # 2. 根據 pos 重構 LIS
        res = [-1] * len(tail)
        j = len(tail) - 1
        for i in range(n-1, -1, -1):
            if pos[i] == j:
                res[j] = nums[i]
                j -= 1
        print(res)
        return len(tail)