在Python中获取最长递增子序列

Question

有人能告诉我为什么这段代码不能产生每个递增的子序列吗？我使用动态规划来解决，但我无法弄清楚为什么这段代码失败了。参数A是一个整数序列。

def LIS(A):

    # make a list of lists
    L = list()
    for i in range(0, len(A)):
        L.append(list())

    #the first increasing subsequence is the first element in A
    L[0].append(A[0])

    for i in range(1, len(A)):
        for j in (0, i):

            # a new larger increasing subsequence found
            if (A[j] < A[i]) and ( len(L[i]) < len(L[j]) ):
                L[i] = L[j]

        L[i].append(A[i])

        # print an increasing subsequence
        print L[i]

这个算法对于A = [3, 5, 10, 0, 1, 100, 2, 4, 7] 的示例输出结果如下：

[3, 5]
[3, 5, 10]
[0]
[1]
[3, 5, 10, 100]
[2]
[3, 5, 10, 100, 4]
[3, 5, 10, 100, 4, 7]
None

正确的输出：

[3] 
[3, 5] 
[3, 5, 10] 
[0] 
[0, 1] 
[3, 5, 10, 100] 
[0, 1, 2] 
[0, 1, 2, 4] 
[0, 1, 2, 4, 7] 

- lambda

---

为什么[0, 1, 100]不是有效的？ - wwii

你在内层循环中尝试做什么似乎并没有起作用，因为你总是将A的第一个项目与A[i]或A[i]与其自身进行比较 - for j in (0, i): 中迭代的不应该是(0,1)。我没有看到任何使用动态规划的证据。 - wwii

在函数中加入一些打印语句以查看发生了什么-使用pprint.pprint(L)作为最后一个语句，在外部循环停止之后。 - wwii

@wwii 这是最长上升子序列问题的动态规划解决方案。 - lambda

我在C++中实现了完全相同的东西并且运行正常。奇怪的Python。 - lambda

我在标题上搞砸了。没有获得0、1、100的原因是3、5、10、100是更长的递增子序列。 - lambda

Answer 1

我在你的代码中发现了两个错误

1.你假设列表是不可变的，但在Python中它们并不是。

L[i] = L[j] this is going to make L[i] point to the same list pointed by L[j]

2.for j in (0, i):

这里的循环不是从0到i-1，而是从0到i。

以下是您代码的修正版本。

def LIS(A):

    # make a list of lists
    L = list()
    for i in range(0, len(A)):
        L.append(list())

    # the first increasing subsequence is the first element in A
    L[0].append(A[0])

    for i in range(1, len(A)):
        for j in range(0, i):

            # a new larger increasing subsequence found
            if (A[j] < A[i]) and (len(L[i]) < len(L[j])):
                'throw the previous list'
                L[i] = []
                'add all elements of L[j] to L[i]'
                L[i].extend(L[j])
        L[i].append(A[i])

    for i in range(len(A)):
    # print an increasing subsequence
        print (L[i])
A = [3, 5, 10, 0, 1, 100, 2, 4, 7]
LIS(A)

- akashchandrakar