Longest Increasing Subsequence

How you get there

1. 1Maintain tails[k] = smallest possible tail of an increasing subsequence of length k+1.
2. 2That array is sorted, so binary search finds where each value belongs.
3. 3Its length is the answer, though its contents are not necessarily a valid subsequence.

Solution

import bisect

def length_of_lis(nums: list[int]) -> int:
    tails: list[int] = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x        # keep the smallest possible tail
    return len(tails)

Time

O(n log n)

Space

O(n)

What goes wrong

Returning `tails` itself as the subsequence is wrong — only its length is meaningful.