编写函数来查找列表中的最长路径（可能是递归？）

Question

我有一个多达50个项目的排序列表，如下所示： [50120160180190250260280300400410475]

我在另一个列表（大约20个）中列出了法律上可能的“空格”： [30,60,70]

基本上，我想用这些空格作为每个值之间的允许值来计算出可能的最长直线

在这种情况下，我们会 50,120,180,250,280 作为我们最长的产品线（5项）

Answer 1

希望我能从你的例子中理解：

base_list = [50,120,160,180,190,250,260,280,300,400,410,475]
spaces = [30, 60, 70]

def calculate(base):
    for i,x in enumerate(base):
        if 0 == i or (base[i] - base[i-1]) in spaces:
            continue
        else:
            del base[i]
            return calculate(base)

    return base

print( calculate(base_list[:]) )

Answer 2

一个可能的简单解决方案是迭代列表，保留符合需求的每个可能子序列的列表

def longest_spaced_subsequence(values, spaces):
    candidates = []
    for element in values:
        # look at each of the subsequences
        for i in range(len(candidates)):
            candidate = candidates[i]

            # if the new element has good spacing from
            # the highest in the candidate, add it.
            if element - candidate[-1] in spaces:
                # make a copy and and add the element to it
                new = list(candidate)
                new.append(element)
                candidates.append(new)

        # maybe this element is the start of the longest sequence
        candidates.append([element])

    return max(candidates, key=len)

这远不是最有效的算法，但它是有效的

这个幼稚的算法有一个地方确实需要改进：它永远保留所有候选列表，因此占用的内存远远超过它所需要的。为了节省内存，您只需要删除不能再扩展的短候选项，这比听起来要复杂一点

正如您在问题标题中所猜测的，递归也可以帮助解决这个问题。你可以采取一种更像Samuel Elh's answer的贪婪方法，但是你不能仅仅返回结果，你必须坚持下去，确保它确实是最长的

Answer 3

记住每个项目以该项目结束的最长路径：

>>> p = {}
>>> for i in items:
        p[i] = max((p.get(i - s, []) for s in spaces), key=len) + [i]

>>> max(p.values(), key=len)
[50, 120, 190, 250, 280]