Python 递归以查找具有特定限制的最长递增子序列-解网

问：

我正在处理一个问题，我需要在 Python 中实现一个递归函数，以从数字列表中找到最长的递增子序列的长度。该列表可以具有任意长度，并且可以包含任何整数。我只允许使用函数和递归来解决这个问题，不允许使用循环、max（）、辅助函数或任何其他内置函数。len()

问题描述如下：

给定一个数字列表，找到创建一系列严格递增的数字的最长子序列的长度。不得更改列表中数字的顺序以产生递增序列，但可以省略数字。

例如，给定列表 [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)

该函数似乎适用于某些输入，但我认为逻辑是有缺陷的。我试图解决这些问题，但我发现想出一个只使用递归和 len（）并且不修改输入列表的解决方案具有挑战性。

我知道当 lst[0] >= lst[1] 时，我的函数应该考虑两种可能性：

放弃当前号码并从下一个号码开始一个新序列，或者
丢弃下一个数字，并尝试使用下一个数字扩展当前序列。

但我正在努力在我的函数中实现这个逻辑。谁能建议我如何改进我当前的实施以正确处理这些情况？

提前感谢您的帮助。

** 对于造成的任何混淆，我们深表歉意。我删除了我提到的违反规则的部分。我想澄清一下，我是初学者，所以我可能会不时犯错误。关于这个问题，我试图通过限制自己只使用 len（）函数并使用递归调用来解决这个问题。

Python 列表算法递归序列

我试图用不同的方法来回答这个问题。基本上，我采用了两个变量，分别表示包含第一个元素和不包括第一个元素的最长递增子序列的长度。我已经尝试了一些测试用例，我将在下面的帖子中包括这些用例。如果以下方法有帮助，请告诉我：include_firstexclude_first

def longest_seq(lst):
    if not lst:  
        return 0
    if len(lst) == 1:  
        return 1
    include_first = 1 + longest_seq(lst[1:]) if lst[0] < lst[1] else 0
    exclude_first = longest_seq(lst[1:])
    return max(include_first, exclude_first)

测试用例：

print("Test Case 1:" ,longest_seq([1, 5, 3, 4]))
print("Test Case 2:", longest_seq([5, 2, 1, 0])) 
print("Test Case 3:", longest_seq([1, 2, 3, 4, 5]))  
print("Test Case 4:", longest_seq([5, 2, 8, 6, 3, 6, 9, 7]))

输出：

Test Case 1: 3
Test Case 2: 1
Test Case 3: 5
Test Case 4: 4

传入输入列表的一部分并删除输入是正确的想法。但是，我建议修改您的函数，以便它跟踪正在考虑的子序列的当前最大元素，因为试图通过保持最大元素（我认为您正在做的事情）来实现这一目标通常行不通。我已经继续提供了关于这可能是什么样子的骨架，但将一些递归调用/细节留空。lst[0]

def longest_seq(lst, largest = None, num = 0):
    if not lst:
        return num

    rest = lst[1:] # the callee operates on the sublist of the lst, with lst[0] excluded
    if num == 0:
        include = longest_seq(rest, lst[0], 1) # In the callee, operate on rest, using lst[0] as the largest element. subsequence length is also 1 in the callee.
        exclude = None # TBD - how would the recursive call for i
        return None # TBD - larger between include/exclude

    # num > 0 => largest entry populated
    exclude = None # figure out the recursive call of not including lst[0]
    if lst[0] > largest: # can include current
        include = None # figure out recursive call
        return None # TBD - larger between include/exclude

    return exclude # could not include lst[0] in the subsequence so only exclude can be returned

1赞 Alain T. 7/4/2023 #3

诀窍是在函数签名中添加一个可选参数，该参数将跟踪最小值（序列中先前包含的数字）。然后，该函数需要将递归时包含与排除第一个数字的结果与列表的其余部分进行比较。

def longest_seq(L,previous=None):
    if not L: return 0
    included = excluded = longest_seq(L[1:],previous)
    if previous is None or L[0]>previous:
        included = 1 + longest_seq(L[1:],L[0])
    return included if included>excluded else excluded

输出：

print(longest_seq([1,5,3,4]))         # 3
print(longest_seq([1,5,3,7,8,9]))     # 5
print(longest_seq([8,1,5,2,7,3,9,4])) # 4

上一个：从序列中删除最小元素数，使第 L 个元素成为第 K 个最大严格前缀最大值

下一个：有必要对路线进行随机排序

Python 递归以查找具有特定限制的最长递增子序列

Python Recursion to Find The Longest Increasing Subsequence with Specific Limitations

评论

评论