python - 最长的公共(public)子序列，python，贪婪

我已经提交了两个序列的lcs问题的代码草案。我在尝试贪婪时犯了错误，现在我已经实现了一个稳定的贪婪算法来解决这个问题。虽然我有两个问题，这是在线课程的一部分，当我提交它时，它说序列[1,2,3]和[3,2,1]的正确输出是1，我相信为什么？所以，我找到了正确的版本并进行了测试，它工作得很好，也就是说输出是0，并且针对正确的版本测试了很多好的测试用例，它工作得很好现在，我有三个问题：
为什么[1,2,3]和[3,2,1]应该输出1而不是0如果我的代码无效，请帮助我处理一些使其无效的测试用例？
谢谢！
我的代码：

def lcs2(a, b):
    lst, tag= [], False
    if len(set(a).intersection(set(b))) != 0: tag = True
    if len(a) <= len(b): x = a; y = b
    else: x = b; y = a
    for i in y:
        if i in x:
            lst.append(x.index(i))
            x[x.index(i)] = None
        else:
            y[i] = None
    cnt = 0
    for i in range(1 ,len(lst)):
        if lst[i] > lst[i-1]: cnt += 1
    if cnt == 0 and not tag: return 0
    return cnt + 1

现在，我把这个放在这里，一些提议似乎实现了一个好的提议：Python: Length of longest common subsequence of lists
但是当测试它的a = [-1, 1, -1, -1, 4]b = [0, -1, 0, 4, 4]时，它对我来说是失败的，这给出了正确的答案2而不是1。

最佳答案

lcs2([1, 2, 3], [3, 2, 1])正确返回1，因为[1]，[2]和[3]都是两次运行中长度为1的序列的示例。
你的算法有一些问题，似乎遗漏了一些情况。其一，它只寻找y中x的某个元素的第一次出现，但不回溯寻找更长的序列。
此外，还不清楚为什么使用tag作为它的唯一功能似乎是检测两个集合的交集是否为空（在这种情况下，结果仅为0，算法应找到1或以上的运行）。
有些运行示例对算法不起作用：print(lcs2([1, 2, 3], [1, 3, 2, 3]))（答案是2，但应该是3）-这是因为缺少回溯；print(lcs2([], [1]))由于尝试使用y[i] = None访问空列表的元素，此操作在索引器中失败。
我不会提供有效的实现，因为https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution有很好的解决方案，不需要在这里复制。
一般来说，不要试图通过考虑随机示例来证明代码，而是尝试考虑具有所有类型变化的示例集合，并针对该集合进行测试。另外，试着完全理解你自己的算法，这样你就可以找出缺陷并可能优化它。

关于python - 最长的公共(public)子序列，python，贪婪，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54120770/