By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,346 Members | 2,331 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,346 IT Pros & Developers. It's quick & easy.

Bug in code of Longest Increasing Subsequence problem

P: 1
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

Expand|Select|Wrap|Line Numbers
  1. def binary_search(t, l, r, key):
  2.     while (r - l > 1):
  3.         m = l + (r - l)//2
  4.         if (t[m]>=key):
  5.             r = m
  6.         else:
  7.             l = m
  8.     return r
  9.  
  10. def LIS():
  11.     tailTable = [0] * N
  12.     tailTable[0] = lst[0]
  13.     len = 1
  14.     for i in range(1, N):
  15.         if (lst[i] < tailTable[0]):
  16.             # New Smallest Value
  17.             tailTable[0] = lst[i]
  18.         elif (lst[i] > tailTable[len - 1]):
  19.             # lst[i] wants to extend largest subsequence
  20.             tailTable[len] = lst[i]
  21.             len += 1
  22.         else:
  23.             # A[i] wants to be current end candidate of an existing
  24.             # subsequence.
  25.             tailTable[binary_search(tailTable, -1, len-1, lst[i])] = lst[i]
  26.  
  27.     return len
  28.  
  29. if __name__ == "__main__":
  30.     N = int(input())
  31.  
  32.     lst = []
  33.     for i in range(N):
  34.         lst.append(input())
  35.     ret = LIS()
  36.     print(ret)
Jul 4 '16 #1
Share this question for a faster answer!
Share on Google+

Post your reply

Sign in to post your reply or Sign up for a free account.