我正在解决一个关于LIS (最长增加子集)的问题,但我无法完全解决它。我在谷歌上搜索了一些解决方案,在 Rosettacode 上我找到了几个。我喜欢这个,因为它看起来很短很直接(很容易理解)。但是它的编写方式使我在重写它时遇到了严重的麻烦。
for i in range(len(d)):
l.append(max([l[j] for j in range(i)
if l[j][-1] < d[i]]
or [[]], key=len)
+ [d[i]]
)
这是我难以理解的部分。这是我认为我理解的:
将解决方案数组中最长的数字组合附加到解决方案数组,低于我从输入数组中考虑的当前数字;加上您正在考虑的输入数组中的数字。(对不起我的英语不好)。
我觉得我没有完全理解代码在做什么。
def longest_increasing_subsequence(d):
'Return one of the L.I.S. of list d'
l = []
for i in range(len(d)):
l.append(max([l[j] for j in range(i) if l[j][-1] < d[i]] or [[]], key=len)
+ [d[i]])
return max(l, key=len)
if __name__ == '__main__':
for d in [[3,2,6,4,5,1], [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]]:
print('a L.I.S. of %s is %s' % (d, longest_increasing_subsequence(d)))