The longest growing subsequence, the algorithm does not work correctly, I do not know why

Question

I made an implementation of the Longest Increasing Subsequence (LIS) algorithm, which, as I see it, will work, but the results are completely messy.

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

Returned result:

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

What it should be:

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

As I saw in the debugger, when we have:

L[i] = L[j]

Not only gets new values , but other lists in the list too ... L[i]main (L)

I do not know how to avoid this. It seems that lists in Python are completely different from vector languages ​​from the C ...

I have been fighting this for a long time. A huge beer to someone who finds what is wrong :(

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)

hoever (, , ). () :

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

3 , , .append for. , :

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() , .

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