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

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 系列的向量语言完全不同...

我为此奋斗了很长时间。给会发现问题的人一大杯啤酒:(

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]]

Note: based on your comment you use python-2.7, from python-3.x there is a method called .copy() on lists that you can call.

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]]

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

Longest increasing subsequence, algorithm works wrong, no idea why

python

algorithm

list

lis