Самая длинная возрастающая подпоследовательность

В информатике задача о самой длинной возрастающей подпоследовательности направлена ​​на поиск подпоследовательности заданной последовательности , в которой элементы подпоследовательности отсортированы в порядке возрастания и в которой подпоследовательность является максимально длинной. Эта подпоследовательность не обязательно является непрерывной или уникальной. Самые длинные возрастающие подпоследовательности изучаются в контексте различных дисциплин, связанных с математикой , включая алгоритмику , теорию случайных матриц , теорию представлений и физику . ^{[1] [2]} Задача о самой длинной возрастающей подпоследовательности разрешима за время , где обозначает длину входной последовательности. ^[3]${\displaystyle O(n\log n),}$${\displaystyle n}$

В первых 16 членах двоичной последовательности Ван дер Корпута

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

одна из самых длинных возрастающих подпоследовательностей — это

0, 2, 6, 9, 11, 15.

Эта подпоследовательность имеет длину шесть; входная последовательность не имеет семичленных возрастающих подпоследовательностей. Самая длинная возрастающая подпоследовательность в этом примере не является единственным решением: например,

0, 4, 6, 9, 11, 15

0, 2, 6, 9, 13, 15

0, 4, 6, 9, 13, 15

— другие возрастающие подпоследовательности равной длины в той же входной последовательности.

Задача о самой длинной возрастающей подпоследовательности тесно связана с задачей о самой длинной общей подпоследовательности , которая имеет решение динамического программирования с квадратичным временем : самая длинная возрастающая подпоследовательность последовательности является самой длинной общей подпоследовательностью и где — результат сортировки. Однако для особого случая, когда входные данные представляют собой перестановку целых чисел, этот подход можно сделать гораздо более эффективным, что приведет к временным ограничениям вида ^[4]${\displaystyle S}$${\displaystyle S}$${\displaystyle Т,}$${\displaystyle Т}$ ${\displaystyle С.}$${\displaystyle 1,2,\ldots ,n,}$${\displaystyle O(n\log \log n).}$

Наибольшая клика в графе перестановок соответствует самой длинной убывающей подпоследовательности перестановки, которая определяет граф (предполагая, что исходная непереставленная последовательность отсортирована от наименьшего значения к наибольшему). Аналогично, максимальный независимый набор в графе перестановок соответствует самой длинной неубывающей подпоследовательности. Поэтому алгоритмы самой длинной возрастающей подпоследовательности могут быть использованы для эффективного решения проблемы клики в графах перестановок. ^[5]

В соответствии Робинсона–Шенстеда между перестановками и таблицами Юнга длина первой строки таблицы, соответствующей перестановке, равна длине самой длинной возрастающей подпоследовательности перестановки, а длина первого столбца равна длине самой длинной убывающей подпоследовательности. ^[3]

Описанный ниже алгоритм эффективно решает задачу самой длинной возрастающей подпоследовательности с массивами и бинарным поиском . Он обрабатывает элементы последовательности по порядку, сохраняя самую длинную возрастающую подпоследовательность, найденную до сих пор. Обозначим значения последовательности как и т. д. Затем после обработки алгоритм сохранит целое число и значения в двух массивах:${\displaystyle X[0],X[1],\ldots ,}$${\displaystyle X[я],}$${\displaystyle L}$

• ${\displaystyle L}$— хранит длину самой длинной возрастающей подпоследовательности, найденной на данный момент.
• ${\displaystyle М[л]}$— хранит индекс наименьшего значения, такого, что существует возрастающая подпоследовательность длины, заканчивающаяся на в диапазоне Явно предположим, что обозначает множество всех индексов, таких что и существует возрастающая подпоследовательность длины, заканчивающаяся на Тогда — это индекс в , для которого минимизируется; это означает, что и (или, что эквивалентно, и для каждого ); если несколько индексов удовлетворяют этому условию, то — наибольший из них.${\displaystyle к}$${\displaystyle X[k]}$${\displaystyle л}$${\displaystyle X[k]}$${\displaystyle k\leq i.}$${\displaystyle K_{i,l}}$${\displaystyle j}$${\displaystyle j\leq i}$${\displaystyle л}$${\displaystyle X[j].}$${\displaystyle k=M[л]}$${\displaystyle K_{i,l}}$${\displaystyle X[M[l]]}$${\displaystyle M[l]\in K_{i,l}}$${\displaystyle X[M[l]]=\min _{j\in K_{i,l}}X[j]}$${\displaystyle M[l]\in K_{i,l}}$${\displaystyle j\in K_{i,l},}$ ${\displaystyle X[M[l]]\leq X[j]}$${\displaystyle М[л]}$
  • Для ясности, «существует возрастающая подпоследовательность длины, заканчивающаяся на » означает, что существуют индексы, заканчивающиеся на такие, что${\displaystyle л}$${\displaystyle X[k]}$${\displaystyle л}$${\displaystyle i_{1}<i_{2}<\cdots <i_{l}=k}$${\displaystyle к}$${\displaystyle X\left[i_{1}\right]<X\left[i_{2}\right]<\cdots <X[k].}$
  • Обратите внимание, что поскольку представляет собой длину возрастающей подпоследовательности, а представляет собой индекс ее окончания.${\displaystyle 1\leq l\leq i+1,}$${\displaystyle l\geq 1}$${\displaystyle k\geq 0}$
  • Длина больше длины , но возможно, что не все элементы в этом массиве используются алгоритмом (фактически, если самая длинная возрастающая последовательность имеет длину , то только используются алгоритмом). Однако если используется/определено , то (и более того, при итерации также будет выполнено). не определено, поскольку последовательности длины не имеют конечного индекса ( может быть любым значением).${\displaystyle М}$${\displaystyle 1}$${\displaystyle X}$${\displaystyle L}$${\displaystyle М[1],\ldots ,М[Л]}$${\displaystyle М[л]}$${\displaystyle l-1\leq M[l]}$${\displaystyle я,}$ ${\displaystyle M[l]\leq i}$${\displaystyle М[0]}$${\displaystyle 0}$${\displaystyle М[0]}$
• ${\displaystyle P[k]}$— сохраняет индекс предшественника в самой длинной возрастающей подпоследовательности, заканчивающейся на${\displaystyle X[k]}$${\displaystyle X[k].}$
  • Длина равна длине${\displaystyle P}$${\displaystyle X,}$
  • Если тогда while не определено, так как не имеет предшественника ( может быть любым значением).${\displaystyle к>0}$${\displaystyle P[k]<k}$${\displaystyle P[0]}$${\displaystyle X[0]}$${\displaystyle P[0]}$

Поскольку приведенный ниже алгоритм использует нумерацию, начинающуюся с нуля , для ясности он дополнен символом , который остается неиспользованным, так что соответствует подпоследовательности длины Реальная реализация может пропускать и корректировать индексы соответствующим образом.${\displaystyle М}$${\displaystyle М[0],}$${\displaystyle М[л]}$${\displaystyle л.}$${\displaystyle М[0]}$

Обратите внимание, что в любой точке алгоритма последовательность увеличивается. Ведь если есть увеличивающаяся подпоследовательность длины, заканчивающаяся на , то есть и подпоследовательность длины, заканчивающаяся на меньшем значении: а именно та, которая заканчивается на Таким образом, мы можем выполнять бинарный поиск в этой последовательности за логарифмическое время.$${\displaystyle X[M[1]],X[M[2]],\ldots ,X[M[L]]}$$${\displaystyle l\geq 2}$${\displaystyle X[M[l]],}$${\displaystyle л-1}$${\displaystyle X[P[M[l]]].}$

Алгоритм, таким образом, выглядит следующим образом:

P = массив длины NM = массив длины N + 1M[0] = -1 // не определено, поэтому может быть установлено любое значениеЛ = 0для i в диапазоне от 0 до N-1: //N-1 включено // Двоичный поиск наименьшего положительного l ≤ L // такой, что X[M[l]] >= X[i] ло = 1 привет = Л + 1 в то время как ло < привет: мид = ло + пол((хай-ло)/2) // ло <= мид < хи если X[M[mid]] >= X[i] привет = середина иначе : // если X[M[mid]] < X[i] ло = середина + 1 // После поиска lo == hi на 1 больше, чем // длина самого длинного префикса X[i] новыйL = ло // Предшественник X[i] — это последний индекс // подпоследовательность длины newL-1 P[i] = M[newL-1] M[newL] = i  если новыйL > L: // Если мы нашли подпоследовательность длиннее любой из // пока не найдено, обновите L L = новыйL// Реконструируем самую длинную возрастающую подпоследовательность// Он состоит из значений X в индексах L:// ..., П[П[М[Л]]], П[М[Л]], М[Л]S = массив длины Lк = М[Л]для j в диапазоне от L-1 до 0: //0 включено S[j] = X[k] к = Р[к]возврат S

Поскольку алгоритм выполняет один бинарный поиск на элемент последовательности, его общее время может быть выражено с использованием нотации Big O , как Фредман (1975) обсуждает вариант этого алгоритма, который он приписывает Дональду Кнуту ; в варианте, который он изучает, алгоритм проверяет, может ли каждое значение быть использовано для расширения текущей самой длинной возрастающей последовательности, за постоянное время, перед выполнением бинарного поиска. С этой модификацией алгоритм использует максимум сравнений в худшем случае, что является оптимальным для алгоритма, основанного на сравнении, вплоть до постоянного множителя в термине . ^[6]${\displaystyle O(n\log n).}$${\displaystyle X[я]}$${\displaystyle n\log _{2}nn\log _{2}\log _{2}n+O(n)}$${\displaystyle O(n)}$

Пример запуска

Согласно теореме Эрдеша–Секереша , любая последовательность различных целых чисел имеет возрастающую или убывающую подпоследовательность длины ^{[7] [8]} Для входных данных, в которых каждая перестановка входных данных равновероятна, ожидаемая длина самой длинной возрастающей подпоследовательности приблизительно равна ^{[9] [2]}${\displaystyle n^{2}+1}$${\displaystyle n+1.}$ ${\displaystyle 2{\sqrt {n}}.}$

В пределе, когда стремится к бесконечности, теорема Бейка-Дейфта-Йоханссона гласит, что длина самой длинной возрастающей подпоследовательности случайно переставленных элементов имеет распределение, приближающееся к распределению Трейси-Уидома , распределению наибольшего собственного значения случайной матрицы в гауссовском унитарном ансамбле . ^[10]${\displaystyle n}$${\displaystyle n}$

Самая длинная возрастающая подпоследовательность также изучалась в условиях онлайн-алгоритмов , в которых элементы последовательности независимых случайных величин с непрерывным распределением — или, альтернативно, элементы случайной перестановки — по одному представляются алгоритму, который должен решить, включать или исключать каждый элемент, без знания более поздних элементов. В этом варианте задачи, который допускает интересные приложения в нескольких контекстах, можно разработать оптимальную процедуру выбора, которая, учитывая случайную выборку размера в качестве входных данных, будет генерировать возрастающую последовательность с максимальной ожидаемой длиной размера приблизительно ^[11] Длина возрастающей подпоследовательности, выбранной этой оптимальной процедурой, имеет дисперсию приблизительно равную , а ее предельное распределение является асимптотически нормальным после обычного центрирования и масштабирования. ^[12] Те же асимптотические результаты справедливы с более точными границами для соответствующей задачи в условиях пуассоновского процесса прибытия. ^[13] Дальнейшее уточнение в установке процесса Пуассона дается посредством доказательства центральной предельной теоремы для оптимального процесса выбора, которая выполняется, с подходящей нормализацией, в более полном смысле, чем можно было бы ожидать. Доказательство дает не только «правильную» функциональную предельную теорему, но и (сингулярную) ковариационную матрицу трехмерного процесса, суммирующую все взаимодействующие процессы. ^[14]${\displaystyle F}$${\displaystyle n}$${\displaystyle {\sqrt {2n}}.}$${\displaystyle {\sqrt {2n}}/3,}$

• Анатолий Вершик  – русский математик (1933–2024), который изучал приложения теории групп к длиннейшим возрастающим подпоследовательностям в случайных перестановках. ^[15]
• Самая длинная чередующаяся подпоследовательность
• Самая длинная общая подпоследовательность  – Алгоритмическая задача на парах последовательностей
• Сортировка терпения  – Алгоритм сортировки – эффективный метод нахождения длины самой длинной возрастающей подпоследовательности.
• Пластический моноид  – моноид положительных целых чисел по модулю эквивалентности Кнута Страницы, отображающие описания викиданных в качестве резерва– алгебраическая система, определяемая преобразованиями, которые сохраняют длину самой длинной возрастающей подпоследовательности.

• Самая длинная возрастающая подпоследовательность алгоритмиста
• Упрощенная длиннейшая возрастающая подпоследовательность
• Нахождение количества самых длинных увеличенных подпоследовательностей