動態規劃最長子序列

動態規劃（Dynamic Programming）是一種解決最優化問題的算法設計策略，它將大問題分解為較小的、相似的子問題，並記錄這些子問題的答案以避免重複計算。最長子序列（Longest Increasing Subsequence，LIS）問題是一個經典的動態規劃問題。

給定一個數列，最長子序列問題旨在找出其中最長的子序列，該子序列的元素各不相同，並且按照遞增順序排列。例如，數列 [2, 3, 1, 2, 4] 的最長遞增子序列是 [1, 2, 2, 4]，長度為4。

動態規劃解決最長子序列問題的算法如下：

1. 初始化一個陣列 dp，其長度與原數列相同，用來記錄每個元素的子序列的最長長度。
2. 初始化 dp[0] = 1，因為每個數列的開頭元素都構成一個長度為1的遞增子序列。
3. 對於數列中的每個元素 i（從 1 到 n-1），找到所有長度為 dp[i-1] 的遞增子序列的末尾元素。
4. 如果數列中的元素 a[i] 大於這些末尾元素，那麼 a[i] 開頭的子序列就是這些子序列的延長，因此 dp[i] = dp[i-1] + 1。
5. 否則，dp[i] 保持不變，因為 a[i] 不能作為任何長度增加的遞增子序列的開頭。
6. 最後，dp 陣列中最大的元素就是最長遞增子序列的長度。

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

def lis(arr):
    n = len(arr)
    dp = [1] * n  # 初始化dp陣列

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

# 示例
arr = [2, 3, 1, 2, 4]
print(lis(arr))  # 輸出: 4

這個算法的時間複雜度為 O(n^2)，空間複雜度為 O(n)。存在更高效的算法，例如使用二分搜尋的版本，其時間複雜度為 O(n log n)，但這是最基礎的動態規劃解法。