最長遞增子序列

最長遞增子序列（Longest Increasing Subsequence，LIS）是一個在數列中尋找最長的元素序列的問題，這些元素序列必須滿足以下條件：

1. 序列中的每個元素都必須來自原始數列。
2. 序列中的每個元素都必須大於或等於其前一個元素。

例如，給定數列 [2, 3, 10, 4, 7, 2]，它的最長遞增子序列是 [2, 3, 4, 7]，長度為 4。

這個問題可以用動態規劃來解決。我們可以定義一個狀態 dp[i] 表示數列中前 i 個元素的最長遞增子序列的長度。根據這個定義，我們可以得到狀態轉移方程：

dp[i] = max(dp[j] + 1) for j < i and a[i] > a[j]

這意味著 dp[i] 是最長遞增子序列的長度，其中這個序列的最後一個元素是 a[i]，並且這個序列的前一個元素來自 a[0] to a[i-1] 中的某個元素。

初始狀態 dp[0] 被定義為 1，因為任何數列的最短遞增子序列都包含它自己。

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

def lis(arr):
    n = len(arr)
    dp = [1] * n  # 初始化最長遞增子序列長度為1

    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, 10, 4, 7, 2]
print(lis(arr))  # 輸出: 4

這個算法的時間複雜度為 O(n^2)，空間複雜度為 O(n)。對於較大的數列，這個算法可能會很慢。存在一些線性時間的算法來解決這個問題，例如二分查找和貪心算法。