У меня есть набор целых чисел. Я хочу найти самую длинную возрастающую подпоследовательность этого набора, используя динамическое программирование.
215
У меня есть набор целых чисел. Я хочу найти самую длинную возрастающую подпоследовательность этого набора, используя динамическое программирование.
Ответы:
Хорошо, сначала я опишу самое простое решение - O (N ^ 2), где N - размер коллекции. Также существует решение O (N log N), которое я также опишу. Смотреть здесь это в разделе Эффективные алгоритмы.
Я предполагаю, что индексы массива находятся в диапазоне от 0 до N - 1. Итак, давайте определим,
DP[i]
что это длина LIS (самая длинная возрастающая подпоследовательность), которая заканчивается в элементе с индексомi
. Чтобы вычислить,DP[i]
мы смотрим на все индексыj < i
и проверяем, еслиDP[j] + 1 > DP[i]
иarray[j] < array[i]
(мы хотим, чтобы это увеличивалось). Если это правда, мы можем обновить текущий оптимум дляDP[i]
. Чтобы найти глобальный оптимум для массива, вы можете взять максимальное значение изDP[0...N - 1]
.Я использую массив,
prev
чтобы позже можно было найти фактическую последовательность, а не только ее длину. Просто вернитесь рекурсивно изbestEnd
цикла с помощьюprev[bestEnd]
.-1
Значение является знак остановки.Хорошо, теперь к более эффективному
O(N log N)
решению:Пусть
S[pos]
будет определено как наименьшее целое число, которое заканчивается возрастающей последовательностью длиныpos
. Теперь переберите каждое целое числоX
входного набора и сделайте следующее:Если
X
> последний элемент вS
, то добавьтеX
в конецS
. Это существенно означает, что мы нашли новый по величинеLIS
.В противном случае найдите наименьший элемент в
S
,>=
чемX
, и измените его наX
. ПосколькуS
сортируется в любое время, элемент можно найти с помощью двоичного поиска вlog(N)
.Общее время выполнения -
N
целые числа и бинарный поиск для каждого из них - N * log (N) = O (N log N)Теперь давайте сделаем реальный пример:
Коллекция целых чисел:
2 6 3 4 1 2 9 5 8
шаги:
Таким образом, длина LIS
5
(размер S).Чтобы восстановить фактическое,
LIS
мы снова будем использовать родительский массив. Позвольтеparent[i]
быть предшественником элемента с индексомi
вLIS
конце в элементе с индексомi
.Чтобы упростить задачу, мы можем сохранить в массиве
S
не фактические целые числа, а их индексы (позиции) в наборе. Мы не держим{1, 2, 4, 5, 8}
, но держим{4, 5, 3, 7, 8}
.То есть вход [4] = 1 , вход [5] = 2 , вход [3] = 4 , вход [7] = 5 , вход [8] = 8 .
Если мы правильно обновим родительский массив, фактическая LIS будет:
Теперь важная вещь - как мы обновляем родительский массив? Есть два варианта:
Если
X
> последний элемент вS
, тоparent[indexX] = indexLastElement
. Это означает, что родительский элемент нового элемента является последним элементом. Мы просто готовимсяX
к концуS
.В противном случае найдите индекс наименьшего элемента в
S
,>=
чемX
, и измените его наX
. Hereparent[indexX] = S[index - 1]
.источник
DP[j] + 1 == DP[i]
тогдаDP[i]
не станет лучше сDP[i] = DP[j] + 1
. Мы пытаемся оптимизироватьDP[i]
.[1,2,5,8]
: 4 идет перед 1 в массиве, как может быть LIS[1,2,4,5,8]
?[2,3,4,5,8]
. Читайте внимательно -S
массивDOES NOT
представляет собой фактическую последовательность.Let S[pos] be defined as the smallest integer that ends an increasing sequence of length pos.
Объяснения Петара Минчева помогли мне все прояснить, но мне было трудно разобрать, что именно, поэтому я сделал реализацию Python с чрезмерно описательными именами переменных и множеством комментариев. Я сделал наивное рекурсивное решение, решение O (n ^ 2) и решение O (n log n).
Я надеюсь, что это помогает прояснить алгоритмы!
Рекурсивное решение
O (n ^ 2) решение для динамического программирования
Решение для динамического программирования O (n log n)
источник
bisect
. Для демонстрации того, как работает алгоритм и его характеристики производительности, я пытался сделать вещи как можно более примитивными.Говоря о решении DP, я обнаружил удивление, что никто не упомянул тот факт, что LIS может быть сокращен до LCS . Все, что вам нужно сделать, это отсортировать копию оригинальной последовательности, удалить все дубликаты и сделать из них LCS. В псевдокоде это:
И полная реализация написана на Go. Вам не нужно поддерживать всю матрицу n ^ 2 DP, если вам не нужно восстанавливать решение.
источник
Следующая реализация C ++ также включает в себя некоторый код, который создает фактическую самую длинную увеличивающуюся подпоследовательность, используя массив с именем
prev
.Реализация без стека просто обратный вектор
источник
Вот три шага оценки проблемы с точки зрения динамического программирования:
Если мы возьмем в качестве примера последовательность {0, 8, 2, 3, 7, 9}, по индексу:
Вот рабочий код C ++ 11:
источник
Вот реализация Scala алгоритма O (n ^ 2):
источник
Вот еще одна реализация O (n ^ 2) JAVA. Нет рекурсии / запоминания для генерации фактической подпоследовательности. Просто строковый массив, который хранит фактическую LIS на каждом этапе и массив для хранения длины LIS для каждого элемента. Довольно чертовски легко. Посмотри:
Код в действии: http://ideone.com/sBiOQx
источник
Это может быть решено в O (n ^ 2) с помощью динамического программирования. Код Python для того же будет выглядеть так:
Для ввода:
5 19 5 81 50 28 29 1 83 23
вывод будет:
[1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5
List_index списка вывода является list_index списка ввода. Значение данного list_index в выходном списке обозначает самую длинную увеличивающуюся длину подпоследовательности для этого list_index.
источник
вот реализация Java O (Nlogn)
источник
Это реализация Java в O (n ^ 2). Я просто не использовал Бинарный поиск, чтобы найти наименьший элемент в S, который>> чем X. Я просто использовал цикл for. Использование бинарного поиска усложнит задачу за O (n logn)
источник
Проверьте код в Java для самой длинной увеличивающейся подпоследовательности с элементами массива
http://ideone.com/Nd2eba
источник
Это может быть решено в O (n ^ 2) с помощью динамического программирования.
Обработайте элементы ввода по порядку и ведите список кортежей для каждого элемента. Каждый кортеж (A, B) для элемента i будет обозначать, A = длину самой длинной увеличивающейся подпоследовательности, заканчивающейся в i, и B = индекс предшественника списка [i] в самой длинной увеличивающейся подпоследовательности, заканчивающейся в списке [i ].
Начните с элемента 1, список кортежей для элемента 1 будет [(1,0)] для элемента i, просканируйте список 0..i и найдите список элементов [k] такой, что list [k] <list [i] значение A для элемента i, Ai будет равно Ak + 1, а Bi будет равно k. Если таких элементов несколько, добавьте их в список кортежей для элемента i.
В конце найдите все элементы с максимальным значением A (длина LIS, заканчивающаяся на элементе) и вернитесь назад, используя кортежи, чтобы получить список.
Я поделился кодом для того же на http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799
источник
O (n ^ 2) Java-реализация:
источник
хотя есть способ, с помощью которого вы можете решить это за время O (nlogn) (это решает за время O (n ^ 2)), но все же этот способ дает подход динамического программирования, который также хорош.
источник
Вот мое решение Leetcode с использованием бинарного поиска: ->
источник
Простейшее решение LIS в C ++ с O (nlog (n)) сложностью по времени
ВЫХОД:
4
источник
Самая длинная возрастающая подпоследовательность (Java)
источник
Я реализовал LIS в Java с использованием динамического программирования и мемоизации. Наряду с кодом я сделал расчет сложности, то есть почему это O (n Log (base2) n). Как мне кажется, теоретические или логические объяснения хороши, но практическая демонстрация всегда лучше для понимания.
Пока я запускал приведенный выше код -
источник
Подход O (NLog (N)), чтобы найти самую длинную возрастающую подпоследовательность
самой Давайте сохраним массив, в котором i-й элемент - это наименьшее возможное число, которым может заканчиваться подпоследовательность размера.
Я намеренно избегаю дальнейших подробностей, так как ответ с верхним голосом уже объясняет это, но этот метод в конечном итоге приводит к аккуратной реализации с использованием заданной структуры данных (по крайней мере, в c ++).
Вот реализация в c ++ (при условии, что требуется строго увеличивающийся самый длинный размер подпоследовательности)
источник