最長遞增子數列

最長遞增子數列（Longest Increasing Subsequence，LIS）是一個在數列中尋找最長的元素遞增子數列的問題。例如，給定數列 [2, 10, 3, 9, 5, 7, 1, 4, 8]，其最長遞增子數列為 [1, 3, 5, 7, 9]，長度為5。

最長遞增子數列問題可以用 Dynamic Programming（動態規劃）來解決。動態規劃的關鍵思想是將大問題分解為小問題來解決，並且記錄已經解決的小問題的答案，以便重複使用。

以下是使用動態規劃解決最長遞增子數列問題的算法：

1. 初始化一個與數列相同長度的陣列 lis，用來存儲每個元素的最長遞增子數列的長度。
2. 設 lis[i] 為數列 A 中元素 A[i] 的最長遞增子數列的長度。
3. 對於每個元素 A[i]，檢查 A[i] 是否大於 A[0] 到 A[i-1] 中的所有元素。如果是，則 lis[i] 為 i（因為 A[i] 可以作為最長遞增子數列的起始元素）。
4. 如果不是，則 lis[i] 為 lis[j] + 1 中最大的那個值，其中 A[j] 是 A[0] 到 A[i-1] 中最大且小於 A[i] 的元素。
5. 最後，最長遞增子數列的長度就是 lis 陣列中的最大值。

以下是一個簡單的Python實現：

def lis(A):
    n = len(A)
    lis = [1] * n  # 初始化每個元素的最長遞增子數列長度為1
    for i in range(1, n):
        for j in range(i):
            if A[i] > A[j] and lis[j] > lis[i]:
                lis[i] = lis[j] + 1
    return max(lis)

# 示例
A = [2, 10, 3, 9, 5, 7, 1, 4, 8]
print(lis(A))  # 輸出最長遞增子數列的長度

這個算法的時間複雜度為 O(n^2)，空間複雜度為 O(n)。對於較大的數列，這個算法可能會比較慢。有時候可以使用二分查找等技巧來加速算法，使其達到 O(n log n) 的時間複雜度。