In this DP/binary-search algorithm, `tail[i]`

stores the smallest last element of all increasing subsequences with length `i+1`

. `tail`

is originally `[]`

. We update `tail`

as we get more and more numbers from `nums`

.

Important: `tail`

is always strictly increasing! (Note that in the statement of this problem, 'increasing' actually means 'strictly increasing')

Whenever we have a new number `x`

from `nums`

, we can binary-search `tail`

to find out the longest subsequence to prolong. We will update and only update this element of `tail`

.

```
tail = []
for x in nums:
pos = bisect.bisect_left(tail, x) # find the position "pos" so that tail[i] < x for all i < pos
tail[pos:pos+1] = [x] # if tail[pos] exists, update it to be x, otherwise append x
return len(tail)
```

This brilliant idea belongs to @dietpepsi , I just rewrite it. His original post is here.