最长递增子序列，算法工作错误，不知道为什么。

Question

我实现了最长上升子序列（LIS）算法，但结果完全混乱。

def lis():
    #D = map(int, raw_input().split())
    D = [3, 2, 6, 4, 5, 1]
    L = [[] for i in range(len(D))]
    L[0].append(D[0])
    for i in range(len(D)):
        for j in range(0,i):
            if D[i] > D[j]:
                L[i] = L[j]
        L[i].append(D[i])
    print L

返回结果：

[[3], [2, 6, 4, 5], [2, 6, 4, 5], [2, 6, 4, 5], [2, 6, 4, 5], [1]]

应该是什么：

[[3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

当我在调试器中看到以下代码时：

L[i] = L[j]

不仅L[i]获得新值，而且main (L)列表上的其他列表也是如此...

我不知道如何避免这种情况。看起来Python中的列表与C系列向量语言完全不同...

我已经为此奋斗了很长时间。给那位找出问题的人一大杯啤酒:(

- Adamm

Answer 1

当你写下 L[i] = L[j] 时，你并没有复制 列表的内容，而是复制了一个引用：从现在开始，L[i] 和 L[j] 指向同一个列表，通过 L[i] 进行的更改将反映在获取 L[j] 时。

一个简单的修复方法就是直接复制列表：

def lis():
    #D = map(int, raw_input().split())
    D = [3, 2, 6, 4, 5, 1]
    L = [[] for i in range(len(D))]
    L[0].append(D[0])
    for i in range(len(D)):
        for j in range(0,i):
            if D[i] > D[j]:
                L[i] = list(L[j])
        L[i].append(D[i])
    print(L)

但是现在你的算法不再起作用（尽管一开始它也没有起作用）。运行你的（修复后的）代码，你会得到：

>>> lis()
[[3, 3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

第一个列表中出现了两次数字 3，您可以通过在 for 循环之前删除 .append 来解决这个问题。 因此，最终版本是：

def lis():
    #D = map(int, raw_input().split())
    D = [3, 2, 6, 4, 5, 1]
    L = [[] for i in range(len(D))] #removed the next line
    for i in range(len(D)):
        for j in range(0,i):
            if D[i] > D[j]:
                L[i] = list(L[j])
        L[i].append(D[i])
    print(L)

这将产生：

>>> lis()
[[3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

注意：根据您的评论，您使用的是python-2.7。从python-3.x开始，列表有一个名为.copy()的方法，您可以调用它。

- Willem Van Onsem

---

@Adamm：注意你的算法出了问题（其实它已经有问题了）。我认为我已经加入了一个修复方案。 - Willem Van Onsem

我遇到了一个小问题：L[i] = L[j].copy()，AttributeError: 'list' object has no attribute 'copy'。但是我用L[i] = list(L[j])代替它，这样正确吗？ - Adamm

@ Adamm：是的，您是否使用 [tag:python-2.7]？在 [tag:python-3.x] 中可以使用 copy。 - Willem Van Onsem

好的，我已经做出了小改动以适应2.7版本，感谢你的一切，干杯！ - Adamm

Answer 2

重要提示

上面的解决方案是正确的，但如果您尝试它，结果可能对某些情况不正确。 例如-数字的最长递增子序列：

5 1 4 2 3 1 2 9 1

是

1 2 3 9

但是这个解决方案不会出现在算法返回的L列表上。 列表将包括：

1 2 9

需要获取列表L中的最大元素。然后可以附加另一个元素D，因此我们必须添加一个条件。以下是正确的代码：

def lis():
#D = map(int, raw_input().split())
D = [5, 1, 4, 2, 3, 1, 2, 9, 1]
L = [[] for i in range(len(D))]
for i in range(len(D)):
    for j in range(0,i):
        if D[i] > D[j] and len(L[i]) < len(L[j])+1: #added condition
            L[i] = list(L[j])
    L[i].append(D[i])
print(L)

>>lis()
[[5], [1], [1, 4], [1, 2], [1, 2, 3], [1], [1, 2], [1, 2, 3, 9], [1]]

- Adamm