Skip to main content
 首页 » 编程设计

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

2025年05月04日13cmt

谁能告诉我为什么这段代码不产生每个递增的子序列? 我使用动态编程来解决这个问题,但我不明白为什么这段代码会失败。 参数 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]  

请您参考如下方法:

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

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): 

这不会将 j 从 0 迭代到 i-1,而是将 j 从 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)