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

Подпоследовательность сохраняет порядок элементов, но может пропускать некоторые из них. Наибольшая возрастающая подпоследовательность — это самая длинная такая последовательность, которая строго возрастает.

В отличие от подмассива, LIS не обязана быть непрерывной. Можно перескакивать через меньшие числа, чтобы продолжить цепочку.

Пусть dp[i] — длина LIS, которая заканчивается в позиции i. Каждый элемент сам по себе образует подпоследовательность длины не меньше единицы.

Для каждого i рассмотрите все предыдущие j. Если a[j] меньше, расширьте последовательность: dp[i] = max(dp[i], dp[j] + 1).

Результат — наибольшее значение в таблице, поскольку LIS может заканчиваться где угодно, а не только в последней позиции.

Двойной цикл работает за O(n в квадрате). При n около 100000 это слишком медленно и приводит к вердикту о превышении лимита времени.

Быстрый метод хранит список из наименьших возможных конечных элементов для каждой длины подпоследовательности — по аналогии с терпеливой сортировкой.

Для каждого числа двоичным поиском найдите подходящую позицию среди конечных элементов с помощью bisect_left, получив общую сложность O(n log n).

Если позиция находится за концом списка, используйте append, чтобы увеличить LIS. Иначе замените конечный элемент на это меньшее значение.

Когда просмотр завершён, len(tails) — это длина LIS. Сам список не всегда является подпоследовательностью, но его длина всегда точна.

Для неубывающего варианта переключитесь на bisect_right, чтобы одинаковые значения могли продолжать цепочку.

Какой метод находит длину LIS за O(n log n)?

Теперь Вы умеете решать задачу о LIS двумя способами. DP за O(n^2) прост, а метод конечных элементов с двоичным поиском подходит для больших входных данных и укладывается в лимит времени.