最长递增子序列 问题描述:给定一个无序的整数序列a[0..n-1],求其中最长递增(严格)子序列的长度。 例如,a={2,1,5,3,6,4,8,9,7},n=9,其最长递增子序列为{1,3,4,8,9},结果为5。python

最长递增子序列（Longest Increasing Subsequence, LIS）是一个经典的动态规划问题，可以使用斐波那契堆或自底向上的动态规划算法来解决。以下是Python代码的一个简单版本，它采用了动态规划的方法：

def lengthOfLIS(nums):
    if not nums:
        return 0
    
    # 初始化列表dp，用于存储以每个元素结尾的最大递增子序列长度
    dp = [1] * len(nums)
    
    for i in range(len(nums)):
        # 遍历所有已计算过的最大递增子序列长度
        for j in range(i):
            # 如果当前元素大于nums[j]，说明它可以加入到以nums[j]结尾的递增子序列中
            if nums[i] > nums[j]:
                # 更新dp[i]为nums[j]结尾的递增子序列长度加一
                dp[i] = max(dp[i], dp[j] + 1)
    
    # 返回整个数组中最长递增子序列的长度，即dp列表中的最大值
    return max(dp)

# 测试例子
nums = [2, 1, 5, 3, 6, 4, 8, 9, 7]
n = len(nums)
print(lengthOfLIS(nums))  # 输出: 5

在这个代码中，我们维护了一个动态规划数组`dp`，它的第`i`个元素表示以`nums[i]`结尾的最长递增子序列的长度。通过比较当前元素与前面元素的关系，我们可以更新这个数组并找到全局最优解。