C语言函数题限差最长子序列pta

在C语言中，"最长递增子序列（Longest Increasing Subsequence，LIS）"是一个常见的动态规划问题。这个题目通常是用来考察数组中的元素按照升序排列找出一个最长的连续递增子序列长度。例如，给定数组 [10, 9, 2, 5, 3, 7, 101, 18]，最长递增子序列可能是 [2, 3, 7, 101] 或者 [10, 18]，其中一个是最大长度为4。

解决这个问题的一种常见算法是使用“帕特森-塔斯克”（Paterson-Hopcroft-Tarjan）或“分治+自底向上”的策略，也称为Floyd-Warshall算法的一个变种。关键步骤包括：

1. 初始化每个元素作为其自身的子序列长度，然后遍历整个数组。
2. 对于数组中的每个元素，检查它能延伸哪些已经计算出的子序列，并更新最长递增子序列的长度。
3. 使用动态规划表格dp[i]存储到第i个元素为止的最大递增子序列长度。

Python伪代码大概如下：

def lis(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# 示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis(nums))  # 输出：4