15,849,829 members
See more:
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, Its giving correct output for some input patterns, But for some its giving incorrect result. Can anybody tell me where is the bug in the code.

What I have tried:

Here is my code
Python
```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)```
Posted
Updated 2-Jul-16 20:55pm
Patrice T 3-Jul-16 1:39am
Give a sample input that give wrong result.

## Solution 1

I am not fluent in Python, but you should try this:
Python
```def LIS():
lenmax = 1
len = 1
for i in range(1, N):
if (lst[i-1] < lst[i]):
# in sequence
len += 1
if (len > lenmax):
lenmax = len
else:
# new sequence
len = 1

return lenmax```

ati229 3-Jul-16 5:27am
@ppolymorphe That's incorrect way to compute Longest Increasing Subsequence
Patrice T 3-Jul-16 5:36am
Can you define what is the correct way, give an example with sequence and result.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 Richard Deeming 40 _Asif_ 30 Richard MacCutchan 20 OriginalGriff 20 Dave Kreskowiak 18
 Richard Deeming 40 _Asif_ 30 Richard MacCutchan 20 OriginalGriff 20 Dave Kreskowiak 20

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900