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

С августа 2021 года по октябрь 2026-го доллар стоил от 414,67 до 549,15 тенге и почти каждый будний день двигался — то вверх, то вниз. Выбросим из этого ряда часть дней так, чтобы в оставшихся курс только рос. Сколько дней удастся сохранить? 151 из 1900. Перебирать наборы дней для этого не нужно: хватает одного прохода по ряду с короткой «лестницей» в руках — для каждой длины цепочки самый низкий курс, которым такая цепочка может кончаться. Сцена строит эту лестницу день за днём; переключайте валюты, правило и порядок дней.

Каждый новый день встаёт на свою ступеньку. Если он выше всех ступенек, лестница становится на одну ступеньку длиннее. Иначе он занимает место первой ступеньки, которая не ниже его. Сколько ступенек в конце, столько и дней в ответе: 151 день, от 423,75 тенге 4 августа 2021 года до 549,15 тенге 2 октября 2025-го — самого дорогого дня ряда. Для этого понадобилось 11 838 сравнений. Таблица «каждый день с каждым» сделала бы 1 804 050.

Дни можно пропускать, и в этом вся разница. Подряд, без пропусков, курс доллара рос не дольше шести дней: выходные обрывают любой рост. Переключите правило на «без спусков» — если соседям в цепочке разрешено стоять на одном курсе, дней станет 269, почти вдвое больше. Причина в календаре: курс на субботу, воскресенье и понедельник почти всегда один и тот же, и нестрогая цепочка подбирает такие тройки целиком. Нажмите «Перемешать»: те же 1900 чисел в случайном порядке дают цепочку всего около 80 дней. А на вкладке «Годы» — средняя температура Алматы за 85 лет: цепочка всё более тёплых лет тянется 21 год, с 1954-го по 2025-й, хотя перемешанные годы дают в среднем 15.

Идея

Наибольшая возрастающая подпоследовательность — самая длинная цепочка элементов, взятых в том же порядке, что в исходной последовательности, но не обязательно подряд, где каждый следующий больше предыдущего. В последовательности 7, 2, 8, 1, 3, 4, 10, 6, 9, 5 такая цепочка — 1, 3, 4, 6, 9 или 2, 3, 4, 6, 9: длина 5, а самих цепочек может быть несколько. Подпоследовательность — не отрезок: найти самый длинный растущий отрезок можно одним проходом со счётчиком, а с пропусками вариантов 2ⁿ.

Из двух цепочек одной длины полезнее та, что кончается ниже: всё, что продолжает высокую, продолжит и низкую. Поэтому для каждой длины k достаточно помнить одно число — самый низкий конец цепочки длины k. Эти концы растут вместе с k, получается лестница. Очередное значение x находит двоичным поиском первую ступеньку, которая не ниже его, и встаёт на её место; если такой нет, над лестницей появляется новая ступенька. Длина лестницы в конце — длина ответа, а саму цепочку восстанавливают указатели: каждый элемент запоминает, кто стоял ступенькой ниже в момент его прихода.

Сначала таблица

Лестница выглядит фокусом, но она выросла из обычной динамики. Что нужно знать о цепочке, чтобы решить, можно ли её продолжить? Только её последний элемент. Значит, состояние — «цепочка, которая кончается на элементе i», а L(i) — её наибольшая длина:

где максимум пустого множества — ноль: элемент сам по себе — цепочка длины 1. Ответ — наибольшее из L(i). Состояние «лучшая цепочка среди первых i элементов» не годится: по нему не узнать, на чём цепочка кончилась, и не проверить, можно ли приписать к ней a_i. Это частая ошибка при первом знакомстве с динамикой: состояние должно хранить ровно то, от чего зависит продолжение.

Таблица честная и короткая, но каждая клетка смотрит на все предыдущие: n(n − 1)/2 сравнений. Для 1900 дней это 1,8 миллиона, для миллиона значений — полтриллиона. Чтобы ускорить, заметим, что большая часть таблицы не нужна. Среди всех j с одинаковым L(j) = k для будущих элементов важен лишь тот, у которого a_j меньше всех: если новый элемент больше какого-то из них, он больше и самого маленького. Вот эти самые маленькие и есть ступеньки лестницы. Самое наглядное объяснение того, как они себя ведут, придумали задолго до компьютерных олимпиад — в виде карточного пасьянса.

Пасьянс

Карты открывают по одной и раскладывают в стопки слева направо. Младшую карту можно положить на старшую или начать ею новую стопку справа от остальных. Цель — закончить с как можно меньшим числом стопок. Разложите колоду сами, а потом переключитесь на «жадно»: каждая карта — на самую левую стопку, куда её можно положить.

Десять карт 7, 2, 8, 1, 3, 4, 10, 6, 9, 5 — пример из обзора Дэвида Олдоса и Перси Диакониса 1999 года. Жадное правило раскладывает их в пять стопок: [7 2 1] [8 3] [4] [10 6 5] [9], от нижней карты к верхней. Пять стопок — и цепочка 1, 3, 4, 6, 9 из пяти карт. Совпадение не случайно.

Из двух половин доказательства сразу следует, что жадное правило лучше любого другого и что число его стопок — длина наибольшей возрастающей подпоследовательности. А верхние карты стопок при жадной раскладке и есть лестница: они растут слева направо, поэтому самую левую подходящую стопку находит двоичный поиск — первая верхняя карта, которая не младше новой. В листингах это bisect_left и sort.SearchInts. Карточная игра превращается в алгоритм за O(n log n).

Олдос и Диаконис предлагают считать пасьянс из 52 карт выигранным, если стопок девять или меньше. В их 10 000 раздачах в среднем выходило 11,6 стопки, а выигрыш — примерно в 5 % случаев. Попробуйте полную колоду в сцене: жадную раскладку не обыграть, но можно проиграть ей, если класть карты наугад.

Код

Обе версии рядом: таблица по определению и пасьянс с указателями назад. Демо раскладывает десять карт из примера и сверяет оба способа на двух тысячах случайных массивов.

Цепочки вышли разные — 1 3 4 6 9 у пасьянса и 2 3 4 6 9 у таблицы, — а длина одна. Какую из равных цепочек выдаст программа, решают мелочи: таблица при равенстве оставляет первого найденного предшественника, пасьянс — того, кто лежал сверху стопки слева. Обе правы.

Теперь настоящие ряды: три валюты к тенге за пять лет и средние температуры Алматы по годам. Курсы хранятся в тиынах, целыми числами, поэтому сравнения точные. Одна функция считает три разные задачи: строго растущую цепочку, неубывающую и строго убывающую.

Ловушка: одна буква в имени функции

bisect_left ищет первую ступеньку, которая не меньше x: равное значение встаёт на место равного, и лестница не растёт. Это строгое возрастание. bisect_right ищет первую ступеньку больше x, и равное значение ставит новую ступеньку над равным — получается неубывающая цепочка. На ряду доллара это 151 день и 269 дней. Обе задачи законные, но путать их нельзя, и на данных с повторами разница огромна. Для убывающей цепочки меняют знак у всех чисел и ищут возрастающую — в листинге так и сделано: у доллара строго убывающая цепочка — 86 дней против 151 дня роста.

Вторая ловушка — принять лестницу за ответ. После десяти карт ступеньки — 1, 3, 4, 5, 9, но такой цепочки в колоде нет: пятёрка пришла последней, уже после девятки. Длину лестница сообщает верно, а сами ступеньки поставлены в разное время и цепочки не образуют. Цепочку восстанавливают только указатели.

Сколько это стоит

Каждый элемент делает один двоичный поиск по лестнице, а в ней не больше L ступенек, где L — длина ответа: время O(n log L), в худшем случае O(n log n). Памяти — L чисел, если нужна только длина, и O(n) указателей, если нужна сама цепочка. Существенно быстрее алгоритм, который только сравнивает элементы, работать не может: Майкл Фредман в 1975 году показал, что лестнице достаточно около n log n − n log log n сравнений и что меньшим числом в худшем случае не обойтись.

Замер на случайных числах: таблица против лестницы.

Наклон таблицы — 2: вдвое длиннее ряд, вчетверо больше работы. Наклон лестницы чуть больше единицы. На четырёх тысячах чисел лестница в Python быстрее таблицы в тысячу раз, а миллион чисел проходит быстрее, чем таблица — восемь тысяч.

Есть и второй способ ускорить таблицу. L(i) — это максимум L по всем прежним элементам со значением меньше a_i, то есть запрос максимума на префиксе по значениям. Если значения сжать в номера от 1 до n, такой запрос отвечает дерево Фенвика за O(log n). Это тоже O(n log n), но гибче: так же считается, например, наибольшая сумма возрастающей подпоследовательности, а лестница с весами не работает — из двух цепочек одной длины низкий конец больше не означает лучшую.

Корень из n

Какой длины цепочка у ряда без всякого порядка? Станислав Улам задал этот вопрос в начале 1960-х и по расчётам методом Монте-Карло предположил, что для случайной перестановки n чисел средняя длина растёт как c√n. Джон Хаммерсли в 1972 году доказал, что предел c существует, а в 1977 году Бенджамин Логан и Лоуренс Шепп и одновременно Анатолий Вершик и Сергей Керов показали, что c = 2. Ещё через двадцать с лишним лет Джинхо Байк, Перси Дейфт и Курт Йоханссон нашли, как длина колеблется вокруг среднего: отклонения порядка n^1/6 подчиняются распределению Трейси — Видома, тому же, что описывает наибольшее собственное значение большой случайной матрицы.

Отсюда и поправка к среднему: оно ближе к 2√n − 1,77·n^1/6, и для 1900 чисел это около 81. Листинг перемешал курсы доллара сто раз и получил в среднем 80,8, хотя наши числа не все различны, а повторы строгую цепочку только укорачивают. Настоящий порядок дней дал 151 — почти вдвое больше: в ряду есть направление.

На этом можно построить грубую проверку на тренд. У 85 лет Алматы цепочка всё более тёплых лет — 21 год. Те же годы, перемешанные тысячу раз, дали в среднем 15,3, а цепочку в 21 год и длиннее — только трижды. Новый, более тёплый год приходит слишком часто, чтобы это было случайностью порядка. Статистику цепочка не заменит: она не говорит, насколько быстро теплеет, и одна выброшенная точка может её изменить. Температура здесь — реанализ ERA5, модельная оценка для ячейки над городом, а не наблюдения одной станции.

Где работает

Перестановка элементов страницы. Когда Vue 3 перерисовывает список с ключами — строки таблицы, карточки, пункты меню, — оставшиеся элементы нужно расставить в новом порядке. Каждый перенос — операция insertBefore над элементом страницы, и их хочется поменьше. Vue выписывает для нового порядка старые номера элементов и находит их наибольшую возрастающую подпоследовательность: эти элементы и так стоят друг относительно друга правильно, их не трогают, а переносят только остальные. Функция в исходниках Vue называется getSequence, и это лестница с указателями назад — та же, что в листингах.

Меньше переносов не бывает: элементы, которых не трогали, сохранили взаимный порядок, а значит, их старые номера в новом порядке растут. Поэтому наименьшее число переносов — n минус длина ответа. Это число — расстояние Улама между двумя перестановками. Как Улам рассказывал Олдосу и Диаконису, он придумал его, размышляя, как быстрее всего упорядочить на руках тринадцать карт бриджа. Переверните список: на месте останется один элемент, переносить придётся все остальные.

diff по уникальным строкам. git diff --patience сначала находит строки, которые встречаются ровно по одному разу и в старом, и в новом файле: заголовки функций, а не пустые строки и скобки. Пары таких строк упорядочены по старому файлу, и нужна самая длинная цепочка, в которой растут и номера в новом — наибольшая возрастающая подпоследовательность. В исходниках git (xdiff/xpatience.c) комментарий описывает лестницу почти нашими словами: для каждой длины хранится одна последовательность — та, у которой последний элемент меньше. Алгоритм придумал Брэм Коэн, в git его добавил Йоханнес Шинделин в 2009 году; чем такой diff отличается от обычного — в статье о diff Майерса.

Общая подпоследовательность. Если в двух строках каждый символ встречается по одному разу, их наибольшая общая подпоследовательность — это наибольшая возрастающая подпоследовательность позиций: выпишем для каждого символа первой строки его место во второй. Когда совпадений мало, этот приём работает и в общем случае — на нём построен алгоритм Ханта и Шиманского 1977 года.

Цепочки по двум признакам. Коробки, которые вкладываются друг в друга, задачи, где важны и срок, и объём, — двумерные цепочки сводятся к одномерной после правильной сортировки. Как именно — во второй задаче ниже.

История

Пасьянс старше алгоритма. По словам Олдоса и Диакониса, название patience sorting дал игре Колин Мэллоуз, а придумал её А. С. К. Росс как практический способ сортировать колоду: в конце раскладки младшая карта лежит сверху самой левой стопки, следующая — сверху какой-то другой, и колоду можно собрать по порядку, снимая верхние карты. Мэллоуз разобрал игру в 1960 году, а опубликовал разбор много позже. Независимо её открыл Роберт Флойд в 1964 году и обсуждал в письмах с Дональдом Кнутом; эта переписка, по словам тех же авторов, так и не была напечатана. Что пасьянс заодно находит наибольшую возрастающую подпоследовательность, независимо заметил Хаммерсли.

Сами подпоследовательности появились в математике ещё раньше, в теореме Эрдёша и Секереша 1935 года. В 1961 году Крейг Шенстед, чтобы изучать наибольшие возрастающие и убывающие подпоследовательности, построил соответствие между перестановками и парами таблиц Юнга: длина первой строки таблицы равна длине наибольшей возрастающей подпоследовательности. Вопрос Улама о случайных перестановках в итоге связал эту комбинаторику со случайными матрицами. А программистам осталась короткая лестница из двоичного поиска, которую Vue запускает всякий раз, когда элементы списка меняются местами.

Задачи

Первая — сцена из начала статьи как задача: самая длинная строго растущая цепочка дней и сами дни, на настоящих курсах и на рядах в сто тысяч дней. Во второй цепочка двумерная: коробки вкладываются друг в друга, и всё решает, как отсортировать коробки с одинаковой стороной.