Решить задачу Longest Increasing Subsequence (LeetCode 300)?

LeetCode 300. Длина самой длинной возрастающей подпоследовательности (не обязательно contiguous). Patience sorting с binary search — O(n log n).

# DP O(n^2)
def lengthOfLIS(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if dp else 0

# Patience sorting O(n log n)
import bisect
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)        # новый max length
        else:
            tails[i] = x           # заменить первый >= x
    return len(tails)

tails[i] — минимальный возможный последний элемент LIS длины i+1. Длина tails в конце — ответ. Восстановить саму подпоследовательность — сложнее (нужен prev pointers). bisect_left для non-decreasing, bisect_right для strictly increasing. Связанные: Russian Doll Envelopes (354), Number of LIS (673).