Задача 05 — длиннейшая возрастающая подпоследовательность (C++)

Глава I. Общая информация

Цель: посчитать длину строго возрастающей подпоследовательности массива за O(n log n), а не за наивные O(n²).
Почему это в Eltex: задача — эталон на «знаешь ли ты приём tails + бинарный поиск поверх DP», а сам паттерн «поддерживать отсортированный массив минимально возможных хвостов и подставлять новый элемент через lower_bound» переиспользуется в задачах на планирование и в сравнении версий (diff-подобные алгоритмы ищут именно длиннейшие совпадающие/растущие подпоследовательности).
Что сдаётся: solution.cpp, проходящий python3 grade.py 05.

Глава II. Что нужно знать до старта

Наивное решение — DP: dp[i] = длина LIS, заканчивающейся на элементе i, пересчитывается перебором всех j < i — O(n²), при 100 000 элементах это ~10¹⁰ операций и тест не пройдёт (ограничение — 2 секунды).

Быстрое решение — «хвосты» (patience sorting): массив tails, где tails[k] — минимально возможный последний элемент возрастающей подпоследовательности длины k+1, накопленной по уже просмотренному префиксу. Массив tails всегда отсортирован по построению, поэтому для каждого нового x бинарным поиском (lower_bound) находится первая позиция с tails[pos] >= x: если такая позиция есть — x заменяет значение в ней (подпоследовательность той же длины, но с меньшим хвостом — выгоднее для будущих продолжений); если позиции нет — x дописывается в конец, увеличивая длину LIS на 1. Именно lower_bound, а не upper_bound — строгое возрастание требует заменить первый элемент >= x, а не > x (иначе повторяющиеся значения ошибочно продлевают подпоследовательность).

Итоговая длина tails в конце обработки массива и есть lis_length. Значения в tails — это не сама LIS, только корректная её длина.

Почему дальше: тот же приём «поддерживай отсортированный инвариант + lower_bound» стоит знать и для задач на минимальное число возрастающих подпоследовательностей на весь массив.

Глава III. Задание

int lis_length(const std::vector<int>& a);   // длина НВП (строго возрастающей)

Требования:

пустая последовательность → 0;
работа за O(n log n); наивное O(n²) не пройдёт проверку на 100 000 элементах (внутренний тест меряет время и роняет прогон при > 2 с);
подпоследовательность не обязана быть непрерывной.

Проверка: python3 grade.py 05. Критерий: все ok, сборка без предупреждений.

Глава IV. Ловушки

upper_bound вместо lower_bound при строгом возрастании → повторяющиеся значения ошибочно продлевают подпоследовательность → длина LIS завышена на массивах с дубликатами (например, [1, 1, 1] должен дать 1, а не 3).
Наивная DP-версия за O(n²) → проходит маленькие тесты, но на 100 000 элементах превышает лимит в 2 секунды → grade.py 05 роняет прогон по таймауту, а не по неверному ответу.
Не обработан пустой вектор отдельным веткой → если код полагается на то, что цикл по пустому диапазону сам вернёт 0, это обычно верно, но стоит явно проверить — тихая логическая ошибка здесь не кидает исключение, просто даёт неверный ответ на пограничном тесте.

Факты для карточек

base | Сложность наивного DP-решения LIS? — O(n²)
core | Сложность решения через tails + бинарный поиск? — O(n log n)
core | Что хранит tails[k]? — минимально возможный последний элемент возрастающей подпоследовательности длины k+1
deep | Почему для строгого возрастания нужен lower_bound, а не upper_bound? — lower_bound находит первый элемент >= x и заменяет его, не давая повторам продлевать подпоследовательность

После сдачи

Разбор: почему массив tails не является самой LIS, а только хранит её длину через минимальные возможные хвосты; как по tails при необходимости восстановить саму подпоследовательность (дополнительный массив предшественников).

6.3 KiB Raw Permalink Blame History Unescape Escape