Python递归实现最长上升子序列问题

最长上升子序列（Longest Increasing Subsequence，简称LIS）是指在给定序列中，找到一个最长的子序列使得它的元素是递增排列的。比如序列 [1, 3, 2, 4, 5, 2, 6] 的最长上升子序列是 [1, 3, 4, 5, 6]。

下面介绍一种利用递归实现最长上升子序列的方法。

首先，我们可以定义一个递归函数 LIS(i)，其中 i 表示当前考虑的子序列的末尾元素的下标。LIS(i) 的返回值即为以元素 i 为结尾的最长上升子序列的长度。

明确了递归函数的定义后，我们需要考虑如何实现它。具体来说，可以遍历从 0 到 i-1 的所有元素，找到其中小于元素 i 的元素 j，然后调用LIS(j)。由于LIS(j)是递归函数，它会返回以元素 j 为结尾的最长上升子序列的长度。我们只需要加上当前元素 i 即可得到以元素 i 为结尾的最长上升子序列的长度。最终的结果即为所有以元素 i 为结尾的可能子序列中的最长上升子序列的最大值。

实现细节上，我们可以使用一个数组 memo 记录已经计算过的 LIS 值。在递归的过程中，如果 memo[i] 已经存在，则直接返回 memo[i]，否则按照上面的方法计算 LIS(i) 并将结果存入 memo[i] 中。

下面是实现最长上升子序列的递归函数的Python代码演示。

def LIS(nums, i, memo):
    if memo[i] != -1:
        return memo[i]
    maxLen = 1
    for j in range(i):
        if nums[j] < nums[i]:
            subLen = LIS(nums, j, memo)
            maxLen = max(maxLen, subLen + 1)
    memo[i] = maxLen
    return maxLen

nums = [1, 3, 2, 4, 5, 2, 6]
memo = [-1] * len(nums)
memo[0] = 1
result = 1
for i in range(1, len(nums)):
    result = max(result, LIS(nums, i, memo))
print(result)

上述代码中，我们首先定义了一个 memo 数组，用于记录已经计算过的 LIS 值。在主函数中，我们遍历数组中的每个元素，调用递归函数 LIS，并将结果和当前最长上升子序列的长度 result 取最大值。

需要注意的是，上述代码只能获取最长上升子序列的长度，如果需要获取最长上升子序列的具体元素，还需要采用其他方法，比如动态规划或二分查找等。

下面以字符串 "pidancode.com" 为例进行演示，获取它的最长上升子序列。

string = "pidancode.com"
nums = [ord(c) for c in string]  # 将字符转换为 ASCII 码值
memo = [-1] * len(nums)
memo[0] = 1
result = 1
for i in range(1, len(nums)):
    result = max(result, LIS(nums, i, memo))
print(result)  # 输出 7，即最长上升子序列的长度

上述代码中，我们首先将字符串转换为 ASCII 码值的列表，然后按照上述方法计算最长上升子序列的长度，最后输出结果 7，即字符串 "pidancode.com" 的最长上升子序列的长度。