最長的遞增子序列

 最長的遞增子序列：

def lis(nums):
    n = len(nums)
    if n == 1:
        return [nums[0]]

    dp = [1] * n  # 記錄每個位置對應的 LIS 長度
    prev = [-1] * n  # 記錄每個位置的前一個元素索引，便於構造 LIS

    # 動態規劃找出最長遞增子序列的長度及其構造
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                prev[i] = j  # 記錄 i 的前一個元素的索引

    # 找到 LIS 的最大長度及其對應索引
    max_len = max(dp)
    idx = dp.index(max_len)

    # 根據 prev 陣列構造最長遞增子序列
    lis_sequence = []
    while idx != -1:
        lis_sequence.append(nums[idx])
        idx = prev[idx]

    # 反轉序列得到正確的順序
    lis_sequence.reverse()
    return lis_sequence

# 測試
nums = list(map(int, list('246813579')))
print(lis(nums))  # 輸出最長遞增子序列

說明：

1. dp 陣列：記錄每個位置為止的最長遞增子序列長度。
2. prev 陣列：記錄每個位置的前一個元素索引，用來構造完整的子序列。
3. 構造序列：從 dp 陣列中找到最大值並從該索引開始，根據 prev 陣列逐步回溯得到完整的最長遞增子序列。
4. 反轉序列：最長遞增子序列是從後往前追蹤的，需反轉回正確順序。

測試輸出：

對於 nums = list(map(int, list('246813579')))，輸出的最長遞增子序列應該是：

[2, 4, 6, 7, 9]