
July 4th, 2016, 01:40 AM
#1
Bug in code of Longest Increasing Subsequence problem
Longest Increasing Subsequence
The Longest Increasing Subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order and in which the subsequence is as long as possible.
I'm trying to implement a program for Longest Increasing Subsequence, It's giving correct output for some input patterns, But for some it's giving incorrect result. Can anybody tell me where is the bug in the code.
Here's my code
Code:
def binary_search(t, l, r, key):
while (r  l > 1):
m = l + (r  l)//2
if (t[m]>=key):
r = m
else:
l = m
return r
def LIS():
tailTable = [0] * N
tailTable[0] = lst[0]
len = 1
for i in range(1, N):
if (lst[i] < tailTable[0]):
# New Smallest Value
tailTable[0] = lst[i]
elif (lst[i] > tailTable[len  1]):
# lst[i] wants to extend largest subsequence
tailTable[len] = lst[i]
len += 1
else:
# A[i] wants to be current end candidate of an existing
# subsequence.
tailTable[binary_search(tailTable, 1, len1, lst[i])] = lst[i]
return len
if __name__ == "__main__":
N = int(input())
lst = []
for i in range(N):
lst.append(input())
ret = LIS()
print(ret)

July 4th, 2016, 07:58 AM
#2
Re: Bug in code of Longest Increasing Subsequence problem
Originally Posted by atinesh229
It's giving correct output for some input patterns, But for some it's giving incorrect result.
Suppose I wanted to help debug your code. I would try the test input patterns, going through the code step by step to see what went right or wrong. But all you said is that "for some it's giving incorrect result". I have no idea what input you tested, so I have to try various input by myself... but why should I do that when you have already done that? It is just a waste of my time (and yours).
Originally Posted by atinesh229
Can anybody tell me where is the bug in the code.
Are you sure that the algorithm is correct?

July 4th, 2016, 11:57 AM
#3
Re: Bug in code of Longest Increasing Subsequence problem
Originally Posted by laserlight
Suppose I wanted to help debug your code. I would try the test input patterns, going through the code step by step to see what went right or wrong. But all you said is that "for some it's giving incorrect result". I have no idea what input you tested, so I have to try various input by myself... but why should I do that when you have already done that? It is just a waste of my time (and yours).
Are you sure that the algorithm is correct?
Test cases that I've tried which worked
Test Case 1: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
Ans : 6
Test Case 2: 1, 12, 7, 0, 23, 11, 52, 31, 61, 69, 70, 2
Ans : 7
Test Case 3: 6, 3, 5, 2, 7, 8, 1
Ans : 4
Test case which is not working is here (Its quite a huge manually cannot be done)
Test Case 4
Use this code to run above the test case.
Actually above test case is from Hacker Rank
Last edited by atinesh229; July 4th, 2016 at 12:00 PM.

July 5th, 2016, 09:48 AM
#4
Re: Bug in code of Longest Increasing Subsequence problem
Here is another implementation if you are interested, which still have the same problem
Code:
from math import ceil
def LIS():
#longest_sequence_indices = [None] * (N+1)
tailTable = [0] * (N+1)
len = 0
for i in range(N):
# Binary Search
low = 1
high = len
while low <= high:
mid = ceil((low + high)/2)
if (tailTable[mid] < lst[i]):
low = mid + 1
else:
high = mid  1
# low will be length of the longest sequence ending at lst[i]
longest_len = low
#longest_sequence_indices[longest_len_here] = i
# The corresponding value
tailTable[longest_len] = lst[i]
if (longest_len > len):
len = longest_len
return(len)
if __name__ == "__main__":
N = int(input())
lst = []
for i in range(N):
lst.append(input())
ret = LIS()
print(ret)
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
