파이썬에서 가장 길게 증가하는 서브 시퀀스 얻기

Question

누구나이 코드가 각각의 증가하는 서브 시퀀스를 생성하지 않는 이유를 말할 수 있습니까? 동적 프로그래밍을 사용하여이 문제를 해결했지만이 코드가 실패한 이유를 알 수 없습니다. 매개 변수 A은 정수 시퀀스입니다. 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] 

출력 예 = 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.You 목록을 가정

코드에서 발견

Answer 1

두 실수는 불변하지만 그들은 파이썬

01에없는

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)