最長遞增子序列python

遞增子序列問題是一個經典的動態規劃問題。這個問題可以轉化為尋找數組中最長的遞增子序列的長度。下面是一個使用Python實現的解決方案：

def lengthOfLIS(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)  # 初始化動態規劃數組，每個位置上的最大值初始為1
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)  # 如果當前元素大於前一個元素，那麼更新dp[i]

    return max(dp)  # 返回dp數組中的最大值，即為最長遞增子序列的長度

# 測試數據
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lengthOfLIS(nums))  # 輸出結果應為3，因為最長遞增子序列是 [2, 3, 7]

這段代碼首先初始化一個動態規劃數組dp，數組中的每個元素表示當前位置的最長遞增子序列的長度。然後遍歷數組中的每個元素，如果當前元素大於前一個元素，那麼就更新dp[i]為dp[j]+1（表示新的最長遞增子序列可以包含當前元素）。最後返回dp數組中的最大值，即為最長遞增子序列的長度。

這段代碼的時間複雜度是O(n^2)，空間複雜度也是O(n)。在實際套用中，如果數組非常大，可能需要最佳化算法以提高效率。