Наибольшая возрастающая подпоследовательность

Наибольшая возрастающая подпоследовательность (LIS) — это самая длинная подпоследовательность массива (не обязательно подряд идущих элементов), в которой значения строго возрастают. Простое ДП решает её за O(n^2), а версия с бинарным поиском — за O(n log n).

Сложность: время O(n log n), память O(n). Идея быстрой версии — поддерживать массив tails минимальных хвостов подпоследовательностей разной длины.

import bisect

def lis(a):
    tails = []
    for x in a:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4