Изменения
Нет описания правки
</code>
== Ещё одно решение за О(NlogN) ==
Существует ещё одно решение, которое позволяет нам найти длину наибольшей возрастающей подпоследовательности, но без возможности восстановления данной подпоследовательности. Для этого мы воспользуемся таблом Юнга. Оно обладает таким свойством, что длина первой строки табла и будет являться искомой величиной.
Само табло представляет из себя расположение <tex>n_1</tex>+<tex>n_2</tex>+...+<tex>n_M</tex> различных целых чисел в массиве строк,выровненных по левому краю, где в ''i''-той строке содержится <tex>n_i</tex> элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Чтобы построить табло требуется прочитать очередной элемент ''a'', если он больше либо равен <tex>n_j</tex>, где j - длина строки, то просто добавить в конец строки, если меньше, то требуется найти первый элемент ''b'', который больше данного ''a''. Поставить элемент ''а'' вместо ''b''. С элементом ''b'' требуется провести те же действия, что и с ''a'', только уже на ''i''+1 строке табла.
Пример построения табла на массиве а (индексация ведётся от 0) :
а : 3,4,9,2,5,1
1 : Берём 3, видим, что 3>0, который расположен на первой строке в ячейке с индексом ''j''=0. Увеличиваем ''j'' и в ''t[i,j]''=3
t =
3
2 : Берём 4, видим, что 4>3. Увеличиваем ''j'' и в ''t[i,j]''=4
t =
3,4
3 : Аналогично с 9
t =
3,4,9
4 : Берём 2. 2<9, то бин. поиском находим нужную нам позицию ''z'', такую, что ''a[i,z-1]''<=2<''a[i,z]''. В данном случае это
первая позиция. Ставим на место ''a[i,z]'' 2 и проделываем такую же операцию, как и для 2, но на строке с индексом ''i''+1.
t =
2,4,9
3
5 : Аналогично с 5
t=
2,4,5
3,9
6 : Аналогично для 1
t =
1,4,5
2,9
3
При построении нам потребуется лишь первая строка, поэтому хранить остальные не имеет смысла.
== Источники ==
* [http://informatics.mccme.ru/moodle/mod/book/view.php?id=488 Наибольшая возрастающая подпоследовательность (НВП, Longest Increasing Subsequence, LIS)]
