最長不下降子序列

最長不下降子序列（Longest Increasing Subsequence, LIS）是一個在數列中找出最長的子序列的算法問題，其中子序列中的每個元素都必須大於或等於前一個元素。

例如，給定數列 [10, 22, 9, 33, 21, 50, 41]，它的最長不下降子序列是 [10, 22, 33, 50, 41]，長度為5。

最長不下降子序列問題可以用動態規劃來解決。動態規劃算法的基本思想是：將原問題分解為若干個子問題，遞歸地求解這些子問題，並保存每個子問題的答案，以便下次需要時可以直接使用，而不是重新計算。

對於最長不下降子序列問題，我們可以定義一個數組 dp，其中 dp[i] 表示數列中前 i 個元素的最長不下降子序列的長度。我們可以使用以下動態規劃方程來計算 dp[i]:

dp[i] = max(dp[i - 1], dp[j] + 1)

其中 j 是滿足 a[i] >= a[j] 的 dp[j] 中最小的值。

初始時，dp[0] = 1，表示空序列的長度為1。

我們可以通過遍歷整個數列來計算 dp 數組，然後找出 dp 數組中最大的值，這個值就是最長不下降子序列的長度。

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

def lis(nums):
    n = len(nums)
    dp = [1] * n  # 初始化 dp 數組
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# 測試
nums = [10, 22, 9, 33, 21, 50, 41]
print(lis(nums))  # 輸出最長不下降子序列的長度

這個算法的時間複雜度為 O(n^2)，空間複雜度為 O(n)。對於較大的數列，這個算法的效率可能不高。在實際套用中，通常會使用二分查找等最佳化技巧來提高算法的效率。