Idea: keep an array *best* that stores for each index *i* the lowest ending value of a subsequence with length *i+1*.

- best[0] = lowest value found so far
- best[1] = lowest ending value of a subsequence with length 2 found so far
- best[2] = lowest ending value of a subsequence with length 3 found so far

And so on

In the end, the elements of **best** will contain *one* of the longest subsequences. It's length is the answer of the problem.

To have an **O(n logn)** time complexity, for each of the **n** elements in the input array *nums*, we binary-search the element of **best** to be updated.

*best* has at most **n** elements, eventually much less (worst case being an increasingly sorted input array), hence the **logn**.

For the example input *[10,9,2,5,3,7,101,18]*, *best* will be in the end *[2, 3, 7, 18]*, with length 4.

```
class Solution(object):
def lengthOfLIS(self, nums):
if not nums: return 0
best = [nums[0]]
for i in range(1, len(nums)):
index = self.upperBound(best, nums[i], 0, len(best))
if index == len(best): best.append(nums[i])
else: best[index] = nums[i]
return len(best)
# Return smallest index i such that array[i] >= target
# or return end+1 if none (target > all array elements)
def upperBound(self, array, target, start, end):
if start >= end: return start
m = (end+start)//2
if array[m] >= target:
if m == start or array[m-1] < target: return m
return self.upperBound(array, target, start, m)
return self.upperBound(array, target, m+1, end)
```