最长递增子序列

最長遞增子序列（Longest Increasing Subsequence，LIS）是一個在數組中找到的子序列，該子序列的元素是遞增的，並且在該數組中沒有更長的遞增子序列。

例如，對於數組 [2, 3, 1, 6, 5, 7, 4]，其最長遞增子序列為 [1, 3, 5, 7]，因為它是可能的最大長度，且元素是遞增的。

最長遞增子序列問題是一個經典的動態規劃問題，可以通過動態規劃算法來解決。動態規劃算法的基本思想是定義一個狀態，該狀態表示解決子問題所需的信息，然後使用這些狀態來構建一個決策過程，從而找到最優解。

對於最長遞增子序列問題，我們可以定義狀態 dp[i] 為以 A[i] 結尾的最長遞增子序列的長度。我們可以使用以下動態規劃方程來計算這個狀態：

dp[i] = 1 + max(dp[j] where A[j] < A[i] and j < i)

這個方程的意思是，以 A[i] 結尾的最長遞增子序列的長度，等於以 A[i-1] 結尾的最長遞增子序列的長度，加上 1，如果存在的話。如果不存在這樣的子序列，則 dp[i] 為 1。

我們可以使用一個循環來計算 dp[i] 的值，然後找到最大的 dp[i] 來找到最長遞增子序列的長度。我們可以使用一個堆疊來找到實際的子序列。

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

def lis(A):
    n = len(A)
    dp = [1] * n  # 初始化狀態
    for i in range(1, n):
        for j in range(i):
            if A[i] > A[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    max_len = max(dp)
    lis = []
    for i in range(n):
        if dp[i] == max_len:
            lis.append(A[i])
    return lis

# 示例
A = [2, 3, 1, 6, 5, 7, 4]
print(lis(A))  # 輸出: [1, 3, 5, 7]

這個算法的時間複雜度為 O(n^2)，空間複雜度為 O(n)。對於較大的數組，這個時間複雜度可能太高。我們可以使用二分查找等技巧來最佳化這個算法，使其時間複雜度為 O(n log n)。