仅用递归与len()实现Python最长严格递增子序列长度求解

问题要求 #

给定数字列表，找出严格递增的最长子序列长度（子序列需保持原元素顺序，可跳过元素）。实现约束：

• 仅允许使用len()函数和递归
• 禁止使用循环、max()、辅助函数或其他内置函数

示例：输入[1,5,3,4]，最长递增子序列为[1,3,4]，长度为3。

原代码缺陷分析 #

原尝试代码如下：

def longest_seq(lst, num=0):
    if not lst:
        return num
    if len(lst) == 1:
        return num + 1

    if lst[0] < lst[1]:
        return longest_seq(lst[1:], num + 1)
    if lst[0] >= lst[1]:
        if lst[0] < lst[2]:
            return longest_seq([lst[0]] + lst[2:], num)
        else:
            return longest_seq(lst[1:], num)

核心问题：

1. 仅处理相邻元素的局部情况，未覆盖所有可能的子序列分支
2. 当lst[0] >= lst[1]时，仅选择单一分支，未比较“丢弃当前元素”和“丢弃下一个元素”两种选择的结果，无法得到真正的最长长度
3. 依赖lst[2]的存在，当列表长度为2时会触发索引越界错误

改进后的递归实现 #

基于“每个元素选或不选”的递归分支逻辑，同时用if-else替代max()完成大小比较，代码如下：

def longest_seq(lst, prev=None):
    # 基准情况：空列表返回0
    if len(lst) == 0:
        return 0
    
    # 分支1：不选择当前第一个元素，递归处理剩余列表
    exclude_len = longest_seq(lst[1:], prev)
    
    # 分支2：如果当前元素可加入子序列，则选择它并递归处理剩余列表
    include_len = 0
    if prev is None or lst[0] > prev:
        include_len = 1 + longest_seq(lst[1:], lst[0])
    
    # 比较两个分支的结果，返回较大值
    if include_len > exclude_len:
        return include_len
    else:
        return exclude_len

逻辑说明 #

1. 基准情况：当列表为空时，子序列长度为0
2. 分支选择：
   • exclude_len：不选当前元素，直接递归计算剩余列表的最长子序列长度
   • include_len：如果当前元素大于子序列的最后一个元素（或还未选择任何元素），则选择该元素，递归计算剩余列表的最长子序列长度后加1
3. 结果比较：用if-else判断两个分支的长度，返回较大值，替代max()的功能

测试示例 #

输入longest_seq([1,5,3,4])，递归过程会遍历所有可能的子序列分支，最终返回正确结果3。

内容的提问来源于stack exchange，提问作者Saiko