Error in Longest Increasing Subsequence in Python

Question

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!

My bad. Should have mentioned that. Have edited the question. — Stuxen
– Stuxen, Commented Sep 30, 2018 at 8:23
Why are [3, 6], [3, 4], [3, 5], [3, 4, 5], [2, 5] and [4, 5] not in your expected output? — blhsing
– blhsing, Commented Sep 30, 2018 at 8:23
New to dynamic programming. The link says that:L[i] contains the longest increasing subsequence that ends in D[i] — Stuxen
– Stuxen, Commented Sep 30, 2018 at 8:26
@blhsing Read the definition on the site. The LIS searches for the longest ascending subsequence that ends with the value of D[i] — Felix
– Felix, Commented Sep 30, 2018 at 8:28

iBug · Accepted Answer · 2018-09-30 08:47:23Z

1

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.

answered Sep 30, 2018 at 8:47

iBug

37.6k8 gold badges101 silver badges155 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Stuxen Over a year ago

Its getting timeout at Hackerrank for few test cases. Is it because of the long time in copying?

iBug Over a year ago

@DeepBodra Of course. You need to optimize the code (in other ways).

Stuxen Over a year ago

Thanks a lot for your help. Oh! coding is so tricky! Found that copying using ":" is the fastest way to copy. Looks like I will have to search for more efficient algorithms

iBug Over a year ago

@DeepBodra Yes. You probably shouldn't be copying the list. You would like to instead "create information about the previous lists" and reconstruct the lists at the end.

Collectives™ on Stack Overflow

Error in Longest Increasing Subsequence in Python

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related