Longest Increasing Subsequence (LIS).

In Simple Words: Patience Sorting with Binary Search ($O(N \log N)$): Maintain array tails. For each number, binary search for the first element $\ge num$ in tails and overwrite it; if none exists, append num. Length of tails is the answer.

• Time: $O(N \log N)$ | Space: $O(N)$

import bisect

def lengthOfLIS(nums: list[int]) -> int:
    tails = []
    for n in nums:
        idx = bisect.bisect_left(tails, n)
        if idx == len(tails):
            tails.append(n)
        else:
            tails[idx] = n
    return len(tails)