Longest Increasing Subsequence

Пройдитесь по списку и примите по одному решению для каждого элемента: оставить его или пропустить. Вы можете оставить nums[i], только если он больше последнего оставленного значения. Рекурсивная функция longest(i, prev) отвечает на вопрос: если последний оставленный элемент находится по индексу prev (или -1, если пока ничего не оставлено), сколько ещё элементов можно добавить, начиная с индекса i?

Если пропустить элемент, получится longest(i+1, prev). Если оставить его, когда это разрешено, получится 1 + longest(i+1, i). Ответом будет большее из этих двух значений, а за концом списка уже ничего нельзя добавить, поэтому результат там равен 0. Каждая возрастающая подпоследовательность представляет собой один путь из решений оставить или пропустить, поэтому поиск не может упустить наилучшую последовательность.

Этот способ работает медленно, потому что обе ветви продолжаются, когда значения возрастают. Для списка вида 1, 2, 3, ..., n число вызовов удваивается с каждым элементом: 2 в степени 40 — это уже примерно 10^12 вызовов, а в больших тестах 2500 элементов. Однако longest(i, prev) зависит только от пары (i, prev), поэтому существует не более n² разных вопросов. Следующий подход — задать каждый из них только один раз.

Состояние. Пусть ending[i] — длина наибольшей возрастающей подпоследовательности, последний элемент которой — nums[i]. Фиксация последнего элемента позволяет легко разделить задачу: если известно, где заканчивается подпоследовательность, понятно, какие последующие значения могут идти после неё.

Рекуррентное соотношение. Если подпоследовательность, заканчивающаяся на nums[i], содержит больше одного элемента, то перед nums[i] стоит некоторый nums[j], где j < i и nums[j] < nums[i], а подпоследовательность до него должна быть как можно длиннее. Поэтому ending[i] = 1 + max(ending[j]) для таких j. Базовый случай: каждый элемент сам по себе является подпоследовательностью, поэтому начальное значение ending[i] равно 1. Порядок: для вычисления ending[i] используются только меньшие индексы, поэтому заполняй таблицу слева направо.

Для [3, 1, 8, 2, 5, 9, 4, 7] таблица имеет вид [1, 1, 2, 2, 3, 4, 3, 4]. Например, перед 5 могут идти 3, 1 или 2, и лучший из них — 2, для которого ending = 2, поэтому ending[4] = 3. Ответ — наибольшее значение, 4, а не последнее: лучшая подпоследовательность может заканчиваться где угодно.

Для каждого индекса проверяется каждый предшествующий индекс, поэтому выполняется n(n-1)/2 сравнений — около 3.1 × 10^6 при n = 2500.

Таблица выше хранит по одному значению длины для каждого индекса. Можно хранить меньше: для каждой длины — только наименьшее значение, которым может заканчиваться возрастающая подпоследовательность этой длины. Обозначим его tails[k] для длины k+1. Меньшее конечное значение всегда не хуже, потому что любое значение, которое может следовать за подпоследовательностью, заканчивающейся на 9, также может следовать за подпоследовательностью, заканчивающейся на 5.

tails всегда отсортирован по возрастанию: подпоследовательность длины k+2, заканчивающаяся на t, содержит подпоследовательность длины k+1, заканчивающуюся значением меньше t. Поэтому для каждого нового значения x выполни двоичный поиск первого хвостового значения, которое ≥ x. Если такого значения нет, x больше любого хвостового значения и увеличивает длину самой длинной подпоследовательности, поэтому добавь его. В противном случае замени это хвостовое значение на x: подпоследовательность на единицу короче заканчивается значением меньше x, поэтому добавление x даёт ту же длину с меньшим конечным значением.

Для [3, 1, 8, 2, 5, 9, 4, 7] массив tails принимает значения [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7], а его длина 4 — это ответ. На шаге [1, 2, 4, 9] число 4 идёт во входных данных после числа 9, поэтому tails сам по себе не является подпоследовательностью; значение имеет только его длина. Этот метод также называют терпеливой сортировкой — по карточной игре, где каждое хвостовое значение является верхней картой в стопке.

Для каждого элемента выполняется один двоичный поиск среди не более чем n хвостовых значений: около 2500 × 12 = 30,000 шагов для входных данных максимального размера.