def lengthOfLIS(self, nums):
def search(lst, lo, hi, target):
if hi  lo < 1:
return lo
mid = lo + (hi  lo)/2
return search(lst, mid+1, hi, target) if lst[mid] < target else search(lst, lo, mid, target)
seq = []
for n in nums:
pos = search(seq, 0, len(seq), n)
if pos >= len(seq):
seq.append(n)
else:
seq[pos] = min(seq[pos], n)
return len(seq)
Python O(NLogN) solution using binary search


Hi, seq means 'sequence' :)
Please refer to https://leetcode.com/discuss/67687/conlognsolutionwithexplainations4ms for more details, we have the same idea, and this guys has a very nice explanation, give him an up vote for me if you like his answer as well.