<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="ru">
		<id>https://nerc.itmo.ru/wiki/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=94.25.229.120&amp;*</id>
		<title>Викиконспекты - Вклад участника [ru]</title>
		<link rel="self" type="application/atom+xml" href="https://nerc.itmo.ru/wiki/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=94.25.229.120&amp;*"/>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%92%D0%BA%D0%BB%D0%B0%D0%B4/94.25.229.120"/>
		<updated>2026-11-17T05:35:56Z</updated>
		<subtitle>Вклад участника</subtitle>
		<generator>MediaWiki 1.30.0</generator>

	<entry>
		<id>https://nerc.itmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%B2%D0%BE%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D1%8E%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8&amp;diff=32825</id>
		<title>Задача о наибольшей возрастающей подпоследовательности</title>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%B2%D0%BE%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D1%8E%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8&amp;diff=32825"/>
				<updated>2013-09-19T10:26:16Z</updated>
		
		<summary type="html">&lt;p&gt;94.25.229.120: /* Решение за O(NlogN) */&lt;/p&gt;
&lt;hr /&gt;
&lt;div&gt;Дан массив из &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt; чисел: &amp;lt;tex&amp;gt;a[0..n - 1]&amp;lt;/tex&amp;gt;. Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.&lt;br /&gt;
{{Определение&lt;br /&gt;
|definition = &lt;br /&gt;
'''Наибольшая возрастающая подпоследовательность (НВП)''' (''англ''. Longest increasing subsequence - LIS)  строки &amp;lt;tex&amp;gt; x &amp;lt;/tex&amp;gt; длины &amp;lt;tex&amp;gt; n &amp;lt;/tex&amp;gt; - это последовательность &amp;lt;tex&amp;gt; x[i_1] &amp;lt; x[i_2] &amp;lt; \dots &amp;lt; x[i_k] &amp;lt;/tex&amp;gt; символов строки &amp;lt;tex&amp;gt; x &amp;lt;/tex&amp;gt; таких, что &amp;lt;tex&amp;gt; i_1 &amp;lt; i_2 &amp;lt; \dots &amp;lt; i_k,  1 \le i_j \le n &amp;lt;/tex&amp;gt;, причем  &amp;lt;tex&amp;gt; k &amp;lt;/tex&amp;gt; - наибольшее из возможных. &lt;br /&gt;
}}&lt;br /&gt;
__TOC__&lt;br /&gt;
== Решение за время O(N&amp;lt;sup&amp;gt;2&amp;lt;/sup&amp;gt;) ==&lt;br /&gt;
Построим массив &amp;lt;tex&amp;gt;d&amp;lt;/tex&amp;gt;, где &amp;lt;tex&amp;gt;d[i]&amp;lt;/tex&amp;gt; &amp;lt;tex&amp;gt;-&amp;lt;/tex&amp;gt; это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом &amp;lt;tex&amp;gt;i&amp;lt;/tex&amp;gt;. Массив будем заполнять постепенно - сначала &amp;lt;tex&amp;gt;d[0]&amp;lt;/tex&amp;gt;, потом &amp;lt;tex&amp;gt;d[1]&amp;lt;/tex&amp;gt; и т.д. Ответом на нашу задачу будет максимум из всех элементов массива &amp;lt;tex&amp;gt;d[]&amp;lt;/tex&amp;gt;.&lt;br /&gt;
Заполнение массива будет следующим: если &amp;lt;tex&amp;gt;d[i] = 1&amp;lt;/tex&amp;gt;, то искомая последовательность состоит только из числа &amp;lt;tex&amp;gt;a[i]&amp;lt;/tex&amp;gt;. Если &amp;lt;tex&amp;gt;d[i] &amp;gt; 1&amp;lt;/tex&amp;gt;, то перед числом &amp;lt;tex&amp;gt;a[i]&amp;lt;/tex&amp;gt; в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент &amp;lt;tex&amp;gt;a[j](j = 0...i - 1)&amp;lt;/tex&amp;gt;, но такой, что &amp;lt;tex&amp;gt;a[j] &amp;lt; a[i]&amp;lt;/tex&amp;gt;. Пусть на каком-то шаге нам надо посчитать очередное &amp;lt;tex&amp;gt;d[i]&amp;lt;/tex&amp;gt;. Все элементы массива &amp;lt;tex&amp;gt;d[]&amp;lt;/tex&amp;gt; до него уже посчитаны. Значит наше &amp;lt;tex&amp;gt;d[i]&amp;lt;/tex&amp;gt; мы можем посчитать следующим образом: &amp;lt;tex&amp;gt;d[i] = 1 + max(d[j]&amp;lt;/tex&amp;gt;, для всех &amp;lt;tex&amp;gt;j = 0...i - 1)&amp;lt;/tex&amp;gt; при условии, что &amp;lt;tex&amp;gt;a[j] &amp;lt; a[i]&amp;lt;/tex&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Пока что мы нашли лишь максимальную длину наибольшей возрастающей подпоследовательности, но саму ее мы вывести не можем. Для восстановления ответа заведем массив &amp;lt;tex&amp;gt;prev[0...n - 1]&amp;lt;/tex&amp;gt;, где &amp;lt;tex&amp;gt;prev[i]&amp;lt;/tex&amp;gt; будет означать индекс в массиве &amp;lt;tex&amp;gt;a[]&amp;lt;/tex&amp;gt;, при котором достигалось наибольшее значение &amp;lt;tex&amp;gt;d[i]&amp;lt;/tex&amp;gt;. Для вывода ответа будем идти от элемента с максимальным значениям &amp;lt;tex&amp;gt;d[i]&amp;lt;/tex&amp;gt; по его предкам.&lt;br /&gt;
&amp;lt;code&amp;gt;&lt;br /&gt;
 vector&amp;lt;int&amp;gt; Find(vector&amp;lt;int&amp;gt; a)&lt;br /&gt;
     int n = a.size();//размер исходной последовательности&lt;br /&gt;
     vector&amp;lt;int&amp;gt; prev(n);&lt;br /&gt;
     vector&amp;lt;int&amp;gt; d(n);&lt;br /&gt;
     for i = 0...n - 1&lt;br /&gt;
         d[i] = 1;&lt;br /&gt;
         p[i] = -1;&lt;br /&gt;
         for j = 0...i - 1&lt;br /&gt;
             if a[j] &amp;lt; a[i]&lt;br /&gt;
                 if d[j] + 1 &amp;gt; d[i]&lt;br /&gt;
                     d[i] = d[j] + 1;&lt;br /&gt;
                     prev[i] = j;&lt;br /&gt;
     int length = d[0], pos = 0;//length - длина наибольшей подпоследовательности, pos - последний символ наибольшей возрастающей подпоследовательности&lt;br /&gt;
     for i = 0...n - 1&lt;br /&gt;
         if d[i] &amp;gt; length&lt;br /&gt;
             length = d[i];&lt;br /&gt;
             pos = i;&lt;br /&gt;
     vector&amp;lt;int&amp;gt; answer;&lt;br /&gt;
     while pos != -1&lt;br /&gt;
         answer.push_back(a[pos]);&lt;br /&gt;
         pos = prev[pos];&lt;br /&gt;
     reverse(answer);&lt;br /&gt;
     return answer;    &lt;br /&gt;
&amp;lt;/code&amp;gt;&lt;br /&gt;
== Решение за O(NlogN) ==&lt;br /&gt;
Для более быстрого решения данной задачи построим следующую динамику: пусть &amp;lt;tex&amp;gt;d[i](i = 0...n)&amp;lt;/tex&amp;gt; - число, на которое оканчивается возрастающая последовательность длины &amp;lt;tex&amp;gt;i&amp;lt;/tex&amp;gt;, а если таких чисел несколько - то наименьшее из них. Изначально мы предполагаем, что &amp;lt;tex&amp;gt;d[0] = -&amp;lt;/tex&amp;gt;&amp;lt;tex&amp;gt;\infty&amp;lt;/tex&amp;gt;, а все остальные элементы &amp;lt;tex&amp;gt;d[i] =&amp;lt;/tex&amp;gt; &amp;lt;tex&amp;gt;\infty&amp;lt;/tex&amp;gt;.&lt;br /&gt;
Заметим два важных свойства этой динамики: &amp;lt;tex&amp;gt;d[i - 1]&amp;lt;/tex&amp;gt; &amp;lt;tex&amp;gt;\le&amp;lt;/tex&amp;gt; &amp;lt;tex&amp;gt;d[i]&amp;lt;/tex&amp;gt;, для всех &amp;lt;tex&amp;gt;i = 1...n&amp;lt;/tex&amp;gt;. А так же что каждый элемент &amp;lt;tex&amp;gt;a[i]&amp;lt;/tex&amp;gt; обновляет максимум один элемент &amp;lt;tex&amp;gt;d[j]&amp;lt;/tex&amp;gt;. Это означает, что при обработке очередного &amp;lt;tex&amp;gt;a[i]&amp;lt;/tex&amp;gt;, мы можем за &amp;lt;tex&amp;gt; O(\log n) &amp;lt;/tex&amp;gt; c помощью двоичного поиска в массиве &amp;lt;tex&amp;gt;d[]&amp;lt;/tex&amp;gt; найти первое число, которое строго больше текущего &amp;lt;tex&amp;gt;a[i]&amp;lt;/tex&amp;gt; и обновить его.&lt;br /&gt;
Для восстановления ответа будем поддерживать заполнение двух массивов:&amp;lt;tex&amp;gt;pos&amp;lt;/tex&amp;gt; и &amp;lt;tex&amp;gt;prev&amp;lt;/tex&amp;gt;. В &amp;lt;tex&amp;gt;pos[i]&amp;lt;/tex&amp;gt; будем хранить позицию &amp;lt;tex&amp;gt;d[i]&amp;lt;/tex&amp;gt; в &amp;lt;tex&amp;gt;a[i]&amp;lt;/tex&amp;gt;, а в &amp;lt;tex&amp;gt;prev[i]&amp;lt;/tex&amp;gt; - позицию предыдущего элемента для &amp;lt;tex&amp;gt;a[i]&amp;lt;/tex&amp;gt;.&lt;br /&gt;
&amp;lt;code&amp;gt;&lt;br /&gt;
 vector&amp;lt;int&amp;gt; Find(vector&amp;lt;int&amp;gt; a)&lt;br /&gt;
     int n = a.size();&lt;br /&gt;
     int length = 0; &lt;br /&gt;
     int d[n], pos[n], prev[n];&lt;br /&gt;
     prev[0] = -1;&lt;br /&gt;
     d[0] = -INFINITY;&lt;br /&gt;
     for i = 1...n - 1 &lt;br /&gt;
         d[i] = INFINITY;&lt;br /&gt;
     for i = 0...n - 1&lt;br /&gt;
         int j = binsearch(d[], a[i]);&lt;br /&gt;
         if d[j - 1] &amp;lt; a[i] and a[i] &amp;lt; d[j]&lt;br /&gt;
             d[j] = a[i];&lt;br /&gt;
             pos[j] = i;&lt;br /&gt;
             prev[i] = pos[d[j - 1]];&lt;br /&gt;
             length = max(length, j);&lt;br /&gt;
     vector&amp;lt;int&amp;gt; answer;&lt;br /&gt;
     int pos = length;&lt;br /&gt;
     while pos != -INFINITY &lt;br /&gt;
         answer.push_back(a[prev[pos]]);&lt;br /&gt;
         pos = a[prev[pos]];&lt;br /&gt;
     reverse(answer);&lt;br /&gt;
     return answer;&lt;br /&gt;
&amp;lt;/code&amp;gt;&lt;br /&gt;
&lt;br /&gt;
== Источники ==&lt;br /&gt;
* [http://informatics.mccme.ru/moodle/mod/book/view.php?id=488 Наибольшая возрастающая подпоследовательность (НВП, Longest Increasing Subsequence, LIS)]&lt;br /&gt;
* [http://e-maxx.ru/algo/longest_increasing_subseq_log Длиннейшая возрастающая подпоследовательность за O (N log N)]&lt;br /&gt;
* [http://ru.wikipedia.org/wiki/LIS Задача поиска наибольшей увеличивающейся подпоследовательности]&lt;br /&gt;
[[Категория:Дискретная математика и алгоритмы]]&lt;br /&gt;
[[Категория:Динамическое программирование]]&lt;/div&gt;</summary>
		<author><name>94.25.229.120</name></author>	</entry>

	</feed>