-
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, len-1, 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)
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
|