最长上升子序列的代码

最长上升子序列是一个经典的计算机科学问题，通常通过动态规划来解决。下面是一个简单的Python代码示例，用于找到给定整数数组中最长的上升子序列：

def longest_increasing_subsequence(nums):
    if not nums: return []
    
    # 初始化一个长度为n+1的列表，所有元素初始值都设为1（表示至少有一个元素）
    dp = [1] * len(nums)
    
    for i in range(len(nums)):
        for j in range(i):
            # 如果当前元素小于前一个元素，并且dp[j]+1大于dp[i]，说明找到了更长的上升子序列
            if nums[i] > nums[j] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                
    # 找到最大值并返回对应的索引，即最长上升子序列的长度
    max_length = max(dp)
    index = dp.index(max_length)
    # 从nums中反向回溯构建最长上升子序列
    lis = [nums[index]]
    while index != 0:
        index -= 1
        if nums[index] < lis[-1] and dp[index] == dp[index - 1] + 1:
            lis.append(nums[index])
    return lis[::-1]  # 返回最长上升子序列

# 使用示例
numbers = [10, 9, 2, 5, 3, 7, 101, 18]
print(longest_increasing_subsequence(numbers))  # 输出：[10, 2, 3, 7, 101]