5-line O(nlog(n)) Python with readability and explanations

• 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.