```
class Solution(object):
def lengthOfLIS(self, A):
tail_values = []
for v in A:
idx = self.lower_bound(tail_values, v)
if idx == len(tail_values):
tail_values.append(v)
else:
tail_values[idx] = v
return len(tail_values)
# Return the index of the first element in input array A that is smaller
# than the given value v.
def lower_bound(self, A, v):
n = len(A)
if not n:
return 0
start = 0
end = n
while start < end:
mid = start + (end - start) / 2
if A[mid] < v:
start = mid + 1
else:
end = mid
return start
```