我已经实现了三个序列的最长公共子序列的版本，但找不到错误。但是coursera年级的学生说我上一次考试不及格。
这意味着该算法几乎是正确的，但在特定情况下会输出错误的答案。但这是什么情况？
约束条件：列表长度不小于1且不大于100。列表中的数字是-10^9到10^9之间的整数。
import sys
def lcs3(a, b, c):
start_b = 0
start_c = 0
result = []
for i in range(len(a)):
for j in range(start_b, len(b)):
if a[i] == b[j]:
for k in range(start_c, len(c)):
if b[j] == c[k]:
start_b = j+1
start_c = k+1
result.append(a[i])
break
if b[j] == c[k]:
break
return len(result)
def lcs3_reversed(a,b, c):
# check reversed sequence which can be with different order
a_rev = a[::-1]
b_rev = b[::-1]
c_rev = c[::-1]
result = lcs3(a, b, c)
result_reversed = lcs3(a_rev, b_rev, c_rev)
if result == result_reversed:
return result
else:
return result_reversed
if __name__ == '__main__':
input = sys.stdin.read()
data = list(map(int, input.split()))
an = data[0]
data = data[1:]
a = data[:an]
data = data[an:]
bn = data[0]
data = data[1:]
b = data[:bn]
data = data[bn:]
cn = data[0]
data = data[1:]
c = data[:cn]
print(lcs3_reversed(a, b, c))
更新：添加了lcs3_reversed函数来解决您描述的情况。无论如何都不能通过测试用例。
输出应包含公共子序列的长度。例如，对于输入：
3
1 2 3
3
2 1 3
3
1 3 5
输出是2，因为这3个列表的公共部分是（1，3）。
失败案例的运行时间是0.04秒，看起来列表很长，因为我自己的大多数测试工作得更快。
谢谢你的帮助！
更新2：我尝试了另一个版本。首先我们找到2个列表的最长公共子序列，然后在结果和第3个列表中再次使用它。
def lcs2(a, b):
start_b = 0
result = []
for i in range(len(a)):
for j in range(start_b, len(b)):
if a[i] == b[j]:
start_b = j+1
result.append(a[i])
break
return result
def lcs2_reversed(a, b):
# check reversed sequence which can be with different order
a_rev = a[::-1]
b_rev = b[::-1]
result_reversed = lcs2(a_rev, b_rev)[::-1]
return result_reversed
def lcs3_reversed(a, b, c):
lcs2_str = lcs2(a, b)
lcs2_rev = lcs2_reversed(a, b)
lcs3_str_str = lcs2(lcs2_str, c)
lcs3_rev_rev = lcs2_reversed(lcs2_rev, c)
lenghts = [len(lcs3_str_str), len(lcs3_rev_rev)]
return max(lenghts)
if __name__ == '__main__':
an = input()
a = input().split()
bn = input()
b = input().split()
cn = input()
c = input().split()
print(max(lcs3_reversed(a, b, c), lcs3_reversed(a, c, b), lcs3_reversed(b, a, c),
lcs3_reversed(b, c, a), lcs3_reversed(c, a, b), lcs3_reversed(c, b, a)))
此外，我尝试了所有的命令组合，但没有帮助我又不能通过最后一个测试用例。
最佳答案
你的例子有点像：
a = [1,2,7,3,7]
b = [2,1,2,3,7]
c = [1,2,3,1,7]
顺序应该是
[1,2,3,7]（如果我理解正确的话），但问题是a的最后一个元素与b和c的最后一个元素匹配，这意味着start_b和start_c被设置为最后一个元素，因此循环结束。关于python - 三个序列的最长公共(public)子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36119853/