Python编写最长递增子序列

Python编写最长递增子序列可以使用动态规划的方法来解决。下面是一个示例代码：

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp =  * n  # 初始化dp数组，每个元素默认为1

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

    max_length = max(dp)  # 最长递增子序列的长度
    max_index = dp.index(max_length)  # 最长递增子序列的最后一个元素的索引

    # 通过回溯找到最长递增子序列
    lis = [nums[max_index]]
    for i in range(max_index - 1, -1, -1):
        if nums[i] < nums[max_index] and dp[i] == dp[max_index] - 1:
            lis.insert(0, nums[i])
            max_index = i

    return lis

# 测试
nums = [10, 9, 2, 5, 3, 7, 101, 18]
result = longest_increasing_subsequence(nums)
print(result)

上述代码中，我们使用一个dp数组来记录以每个元素结尾的最长递增子序列的长度。然后通过两层循环遍历数组，如果当前元素大于前面的元素，则更新dp数组中对应位置的值。最后，找到dp数组中的最大值和对应的索引，通过回溯找到最长递增子序列。