CODEWITHSUNDEEP
pythonpython-3.xdynamic-programming
Stuxen
Stuxen

Reputation: 738

Error in Longest Increasing Subsequence in Python

I am trying to implement the Longest Increasing Subsequence in Python by refering the video here.

I think I have done it correct. A Dry Run of the code also looks fine to me. But the output is incorrect.

d = [3, 2, 6, 4, 5, 1]
l = []
l.append([d[0]])

for i in range(1, len(d)):
    l.append([])
    for j in range(0, i):
        if d[j] < d[i] and len(l[i]) < len(l[j]) + 1:
            l[i] = l[j]
    l[i].append(d[i])

print(l)

Expected Output: [[3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

Actual Output: [[3], [2, 6, 4, 5], [2, 6, 4, 5], [2, 6, 4, 5], [2, 6, 4, 5], [1]]

Any Help Would Be Appreciated!

Upvotes: 0

Views: 192

Answers (1)

iBug
iBug

Reputation: 37317

This is just another referencing problem.

for i in range(1, len(d)):
    l.append([])
    for j in range(0, i):
        if d[j] < d[i] and len(l[i]) < len(l[j]) + 1:
            l[i] = l[j]
    l[i].append(d[i])

Note the line l[i] = l[j], that makes l[i] the same list as l[j], so when you modify l[i] later, l[j] gets modified too. You probably want a copy here:

l[i] = l[j][:]
l[i] = list(l[j])
l[i] = l[j].copy()  # Python 3.3 or up

These 3 lines are equivalent so pick one you like.

Upvotes: 1

Related Questions