```
class Solution(object):
def find(self,res,end,x):
l = 0
r = end
while l<r:
mi = (l+r)/2
if res[mi] == x: return mi
if res[mi]>x:
r = mi
else:
l = mi+1
return r
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = []
for i in nums:
l = len(res)
index = self.find(res,l,i)
if index==l:
res.append(i)
else:
res[index]=i
return len(res)
```