Created
July 18, 2016 17:22
-
-
Save shahril96/fc5643d29f3af9c9223c8e9074b8e14c to your computer and use it in GitHub Desktop.
Longest increasing sub-sequence solver with complexity of O(n * logn)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def bin_search(lis, x): | |
lo, hi = 0, len(lis)-1 | |
while lo < hi: | |
mid = int((hi+lo)/2) | |
if lis[mid] >= x: | |
hi = mid | |
else: | |
lo = mid+1 | |
return hi | |
_ = int(input()) | |
lis = [] | |
for x in range(_): | |
if len(lis) == 0 or lis[len(lis)-1] < x: | |
lis.append(x) | |
else: | |
s = bin_search(lis, x) | |
lis[s] = x | |
print(len(lis)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment