Задача о наибольшей возрастающей подпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 19 промежуточных версий 7 участников)
Строка 1: Строка 1:
 +
{{Задача
 +
|definition =
 +
Дан массив из <tex>n</tex> чисел: <tex>a[0..n - 1]</tex>. Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.
 +
}}
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Наибольшая возрастающая подпоследовательность (НВП)''' (''англ''. Longest increasing subsequence - LIS)  строки <tex> x </tex> длины <tex> n </tex> - это последовательность <tex> x[i_1] < x[i_2] < \dots < x[i_k] </tex> символов строки <tex> x </tex> таких, что <tex> i_1 < i_2 < \dots < i_k,  1 \le i_j \le n </tex>, причем  <tex> k </tex> - наибольшее из возможных.  
+
'''Наибольшая возрастающая подпоследовательность (НВП)''' (англ. ''Longest increasing subsequence, LIS'')  строки <tex> x </tex> длины <tex> n </tex> {{---}} это последовательность <tex> x[i_1] < x[i_2] < \dots < x[i_k] </tex> символов строки <tex> x </tex> таких, что <tex> i_1 < i_2 < \dots < i_k,  1 \leqslant i_j \leqslant n </tex>, причем  <tex> k </tex> {{---}} наибольшее из возможных.  
 
}}
 
}}
Задача заключается в том, чтобы отыскать это наибольшее <tex> k </tex> и саму подпоследовательность.
+
 
Известно несколько алгоритмов решения этой задачи.
+
__TOC__
==== Пример алгоритма, работающего за время <tex> O(n^2) </tex> ====
+
== Решение за время O(N<sup>2</sup>) ==
Строим таблицу <tex> a[1 \dots n] </tex>. Каждый её элемент <tex> a[i] </tex> - длина наибольшей возрастающей подпоследовательности, оканчивающейся точно в позиции <tex> i </tex>. Если мы построим эту таблицу, то ответ к задаче - наибольшее число из этой таблицы.
+
Построим массив <tex>d</tex>, где <tex>d[i]</tex> {{---}} это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом <tex>i</tex>. Массив будем заполнять постепенно {{---}} сначала <tex>d[0]</tex>, потом <tex>d[1]</tex> и т.д. Ответом на нашу задачу будет максимум из всех элементов массива <tex>d</tex>.
Само построение тоже элементарно: <tex> a[i] = \max{(a[j] + 1)} </tex>,для всех <tex> j = 1\dots i-1</tex>, для которых <tex> x[j] < x[i] </tex>. База динамики <tex> a[1] = 1 </tex>.
+
Заполнение массива будет следующим: если <tex>d[i] = 1</tex>, то искомая последовательность состоит только из числа <tex>a[i]</tex>. Если <tex>d[i] > 1</tex>, то перед числом <tex>a[i]</tex> в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент <tex>a[j](j = 0...i - 1)</tex>, но такой, что <tex>a[j] < a[i]</tex>. Пусть на каком-то шаге нам надо посчитать очередное <tex>d[i]</tex>. Все элементы массива <tex>d</tex> до него уже посчитаны. Значит наше <tex>d[i]</tex> мы можем посчитать следующим образом: <tex>d[i] = 1 + \max\limits_{j = 0 .. i - 1}{d[j]}</tex> при условии, что <tex>a[j] < a[i]</tex>.
Если мы хотим восстановить саму подпоследовательность, то заведем массив предыдущих величин <tex>prev</tex> такой, что <tex>prev[i]</tex> - предпоследний элемент в НВП, оканчивающейся в элементе с номером <tex> i </tex>. Его значение будет изменяться вместе с изменением соответствующего i-ого элемента матрицы <tex>a</tex>.
+
 
 +
Пока что мы нашли лишь максимальную длину наибольшей возрастающей подпоследовательности, но саму ее мы вывести не можем. Для восстановления ответа заведем массив <tex>prev[0...n - 1]</tex>, где <tex>prev[i]</tex> будет означать индекс в массиве <tex>a[]</tex>, при котором достигалось наибольшее значение <tex>d[i]</tex>. Для вывода ответа будем идти от элемента с максимальным значениям <tex>d[i]</tex> по его предкам.
 +
 
 +
===Псевдокод алгоритма===
 
<code>
 
<code>
  int a[MaxN]; //maxN - наибольшая возможная длина возрастающей последовательности
+
  '''vector<int>''' findLIS('''vector<int>''' a):
int prev[maxN];
+
    '''int''' n = a.size                    ''<font color="green">//размер исходной последовательности</font>''
for i = 0 ... n
+
    '''int''' prev[0..n - 1]
        a[i] = 1;
+
    '''int''' d[0..n - 1]
        prev[i] = -1;
+
 
        for j = 0 ... i - 1  
+
    '''for''' i = 0 '''to''' n - 1
                if(a[j] < a[i])
+
        d[i] = 1
                        a[i] = max(a[i], 1 + a[j]);
+
        prev[i] = -1
                        prev[i] = j;
+
        '''for''' j = 0 '''to''' i - 1
int ans = d[0], pos = 0;
+
            '''if''' (a[j] < a[i] '''and''' d[j] + 1 > d[i])
for i = 0 ... n  
+
                d[i] = d[j] + 1
        ans = max(ans, d[i]);
+
                prev[i] = j
        pos = i;
+
 
int it = 0;
+
    pos = 0                            ''<font color="green">// индекс последнего элемента НВП</font>''
int lsa[maxN]; // наибольшая возрастающая последовательность <br>
+
    length = d[0]                     ''<font color="green">// длина НВП</font>''
while(pos != -1) //восстанавливаем предка
+
    '''for''' i = 0 '''to''' n - 1
        lsa[it] = pos;
+
        '''if''' d[i] > length
        pos = prev[pos];
+
            pos = i
        it = it + 1;
+
            length = d[i]
for it - 1 ... 0 // вывод последовательности, начиная с первого элемента
+
   
        write(lsa[it])
+
    ''<font color="green">// восстановление ответа</font>''
 +
    '''vector<int>''' answer
 +
    '''while''' pos != -1
 +
        answer.push_back(a[pos])
 +
        pos = prev[pos]
 +
    reverse(answer)
 +
 
 +
    '''return''' answer   
 
</code>
 
</code>
Для вывода самой подпоследовательности достаточной пройти по массиву <tex>prev</tex>, начиная с номера того элемента, на котором мы зафиксировали наш ответ lis, и спускаясь по его предыдущим элементам, пока не достигнем -1 в предке очередного элемента.
+
== Решение за O(N log N) ==
 +
Для более быстрого решения данной задачи построим следующую динамику: пусть <tex>d[i](i = 0...n)</tex> {{---}} число, на которое оканчивается возрастающая последовательность длины <tex>i</tex>, а если таких чисел несколько {{---}} то наименьшее из них. Изначально мы предполагаем, что <tex>d[0] = -\infty</tex>, а все остальные элементы <tex>d[i] =</tex> <tex>\infty</tex>.
 +
Заметим два важных свойства этой динамики: <tex>d[i - 1] \leqslant d[i]</tex>, для всех <tex>i = 1...n</tex> и каждый элемент <tex>a[i]</tex> обновляет максимум один элемент <tex>d[j]</tex>. Это означает, что при обработке очередного <tex>a[i]</tex>, мы можем за <tex> O(\log n) </tex> c помощью [[Целочисленный_двоичный_поиск|двоичного поиска]] в массиве <tex>d</tex> найти первое число, которое больше либо равно текущего <tex>a[i]</tex> и обновить его.
  
==== Пример алгоритма, работающего за время <tex> O(n\cdot\log n) </tex> ====
+
Для восстановления ответа будем поддерживать заполнение двух массивов: <tex>pos</tex> и <tex>prev</tex>. В <tex>pos[i]</tex> будем хранить индекс элемента, на который заканчивается оптимальная подпоследовательность длины <tex>i</tex>, а в <tex>prev[i]</tex> {{---}} позицию предыдущего элемента для <tex>a[i]</tex>.
Для строки ''x'' будем по-прежнему хранить массивы <tex>a</tex> (<tex>a</tex> уже длины <tex>n + 1</tex>) и <tex>prev</tex>, добавим к ним так же массив <tex>last</tex> из <tex>n + 1</tex> элементов так, что в <tex>last[i]</tex> хранится номер последнего элемента в возрастающей подпоследовательности длины <tex>i</tex>. Теперь <tex> a[i] </tex> содержит наименьший по величине элемент, на который может оканчиваться  возрастающая подпоследовательность длины <tex>i</tex>, среди всех <tex>x[j]</tex>, где <tex>1 \leqslant j \leqslant i-1 </tex>, если мы на шаге <tex>i</tex>. В свою очередь, <tex>prev[i]</tex> хранит индекс предшевствующего символа для наибольшей возрастающей подпоследовательности, оканчивающейся в i-ой позиции. Заметим, что <tex> a[0] < a[1] < a[2] < \dots < a[n] </tex>. Пусть мы находимся на i-ом шаге, тогда нам надо найти такой номер k <tex> a[k] \leqslant x[i] < a[k+1] </tex> (если положить при начальной реализации <tex> a[0] = -\inf</tex> - фиктивный элемент, <tex>a[1] = a[2] = \dots = a[n] = \inf </tex>, то такое k всегда найдется).Причем если в условии не строгое возрастание, то массив <tex>a</tex> ''не убывает'', и надо искать наибольшее k из возможных. После этого полагаем <tex> a[k + 1] = x[i] </tex>, а остальные элементы массива не меняем. В силу упорядоченности массива a, мы можем искать k бинарным поиском (при не строгом возрастании необходимо пользоваться функцией <tex>upperBound(1, n, a[i])</tex>), чтобы найти элемент <tex>a[i]</tex> с максимальным индексом. Параллельно нахождению НВП будем записывать массив предков <tex>prev</tex> и номеров <tex>last</tex>. Подсчитаем время: мы n раз выпоняем бинарный поиск, что требует <tex> O(\log n) </tex> времени. Итого: <tex> O(n\cdot\log n) </tex>.
 
  
 +
===Псевдокод алгоритма===
 
<code>
 
<code>
  lis = 0
+
  '''vector<int>''' findLIS('''vector<int>''' a):
a = (n + 1, inf)
+
    '''int''' n = a.size                    ''<font color="green">//размер исходной последовательности</font>''
prev = (n, -1)
+
    '''int''' d[0..n]
a[0] = -inf
+
    '''int''' pos[0..n]
last[0] = -1
+
    '''int''' prev[0..n - 1]
For i = 1 to n
+
    length = 0
     j = binary_search(0, n, x[i]) // бинарный поиск j < i, удовлетворяющего x[a[j]] < x[i] и x[i] < x[a[j + 1]]
+
   
    d[j + 1] = a[i]
+
    pos[0] = -1
    p[i] = last[j]
+
    d[0] = -INF
     last[j + 1] = i;
+
    '''for''' i = 1 '''to''' n
     If (lis < j + 1)
+
        d[i] = INF
      lis = j + 1;
+
     '''for''' i = 0 '''to''' n - 1
 +
        j = binary_search(d, a[i])
 +
        '''if''' (d[j - 1] < a[i] '''and''' a[i] < d[j])
 +
            d[j] = a[i]
 +
            pos[j] = i
 +
            prev[i] = pos[j - 1]
 +
            length = max(length, j)
 +
      
 +
    ''<font color="green">// восстановление ответа</font>''
 +
    '''vector<int>''' answer
 +
    p = pos[length]
 +
    '''while''' p != -1
 +
        answer.push_back(a[p])
 +
        p = prev[p]
 +
     reverse(answer)
 +
 
 +
    '''return''' answer
 
</code>
 
</code>
Для восстановления самой последовательности необходимой пройти по массиву pred с номера <tex>last[lis]</tex>, выводя элементы НВП в обратном порядке, аналогично действиям в прошлом алгоритме.
 
  
== Источники ==
+
== Ещё одно решение за О(N log N) ==
* [http://informatics.mccme.ru/moodle/mod/book/view.php?id=488 Наибольшая возрастающая подпоследовательность (НВП, Longest Increasing Subsequence, LIS)]
+
Существует ещё одно решение, которое позволяет нам найти длину наибольшей возрастающей подпоследовательности, но без возможности восстановления данной подпоследовательности. Для этого мы воспользуемся таблом Юнга. Оно обладает таким свойством, что длина первой строки табла и будет являться искомой величиной<ref>[https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted_correspondence#Properties Wikipedia {{---}} Robinson–Schensted correspondence]</ref>.
* [http://e-maxx.ru/algo/longest_increasing_subseq_log Длиннейшая возрастающая подпоследовательность за O (N log N)]
+
 
* [http://ru.wikipedia.org/wiki/LIS Задача поиска наибольшей увеличивающейся подпоследовательности]
+
Само табло представляет из себя расположение <tex>n_1+n_2+...+n_M</tex> различных целых чисел в массиве строк, выровненных по левому краю, где в <tex>i</tex> строке содержится <tex>n_i</tex> элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Чтобы построить табло требуется прочитать очередной элемент <tex>a_i</tex>, если он больше либо равен <tex>n_j</tex>, где <tex>j</tex> {{---}} длина строки, то просто добавить в конец строки, если меньше, то требуется найти первый элемент <tex>b</tex>, который больше данного <tex>a_i</tex>. Поставить элемент <tex>a</tex> вместо <tex>b</tex>. С элементом <tex>b</tex> требуется провести те же действия, что и с <tex>a</tex>, только уже на <tex>i+1</tex> строке табла.
 +
 
 +
Пример построения табла на массиве <tex>a = [ 3, 4, 9, 2, 5, 1 ]</tex> :
 +
 
 +
1. Берём элемент <tex>3</tex>. Видим, что <tex>3 > 0</tex>, который расположен на первой строке в ячейке с индексом <tex>j = 0</tex>. Увеличиваем <tex>j</tex> и <tex>t[i][j] = 3</tex>.
 +
 
 +
:{| border = 1; class="wikitable"
 +
|&nbsp;&nbsp;3&nbsp;&nbsp;
 +
|}
 +
 
 +
2. Берём элемент <tex>4</tex>. Видим, что <tex>4 > 3</tex>. Увеличиваем <tex>j</tex> и <tex>t[i][j] = 4</tex>.
 +
 
 +
:{| border = 1; class="wikitable"
 +
|&nbsp;&nbsp;3&nbsp;&nbsp;
 +
|&nbsp;&nbsp;4&nbsp;&nbsp;
 +
|}
 +
 
 +
3. Аналогично для элемента <tex>9</tex>.
 +
 
 +
:{| border = 1; class="wikitable"
 +
|&nbsp;&nbsp;3&nbsp;&nbsp;
 +
|&nbsp;&nbsp;4&nbsp;&nbsp;
 +
|&nbsp;&nbsp;9&nbsp;&nbsp;
 +
|}
 +
 
 +
4. Берём элемент <tex>2</tex>. Так как <tex>2 < 9</tex>, то бинарным поиском находим нужную нам позицию <tex>z</tex>, такую, что <tex>t[i][z-1] \leqslant 2 < t[i][z]</tex>. В данном случае это
 +
первая позиция. Присваиваем <tex>t[i][z] = 2</tex> и проделываем такую же операцию, но для строки с индексом <tex>i+1</tex>.
 +
 
 +
:{| border = 1; class="wikitable"
 +
|-align = "center"
 +
|&nbsp;&nbsp;2&nbsp;&nbsp;
 +
|&nbsp;&nbsp;4&nbsp;&nbsp;
 +
|&nbsp;&nbsp;9&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;3&nbsp;&nbsp;
 +
|}
 +
 
 +
5. Аналогично для элемента <tex>5</tex>.
 +
 
 +
:{| border = 1; class="wikitable"
 +
|-align = "center"
 +
|&nbsp;&nbsp;2&nbsp;&nbsp;
 +
|&nbsp;&nbsp;4&nbsp;&nbsp;
 +
|&nbsp;&nbsp;5&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;3&nbsp;&nbsp;
 +
|&nbsp;&nbsp;9&nbsp;&nbsp;
 +
|}
 +
 
 +
6. Аналогично для элемента <tex>1</tex>.
 +
 
 +
:{| border = 1; class="wikitable"
 +
|-align = "center"
 +
|&nbsp;&nbsp;1&nbsp;&nbsp;
 +
|&nbsp;&nbsp;4&nbsp;&nbsp;
 +
|&nbsp;&nbsp;5&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;2&nbsp;&nbsp;
 +
|&nbsp;&nbsp;9&nbsp;&nbsp;
 +
|-align = "center"
 +
|&nbsp;&nbsp;3&nbsp;&nbsp;
 +
|}
 +
 
 +
Таким образом, длина наибольшей возрастающей подпоследовательности для массива <tex>a</tex> равна <tex>3</tex> (например, подпоследовательность из элементов <tex>[ 3, 4, 9 ]</tex>).
 +
 
 +
 
 +
== См. также ==
 +
*[[Задача о наибольшей общей подпоследовательности]]
 +
*[[Наибольшая общая возрастающая подпоследовательность]]
 +
*[[Задача о наибольшей общей палиндромной подпоследовательности]]
 +
==Примечания==
 +
 
 +
<references />
 +
== Источники информации ==
 +
* [http://ru.wikipedia.org/wiki/LIS Википедия {{---}} Задача поиска наибольшей увеличивающейся подпоследовательности]
 +
* [https://en.wikipedia.org/wiki/Longest_increasing_subsequence Wikipedia {{---}} Longest increasing subsequence]
 +
* [http://informatics.mccme.ru/moodle/mod/book/view.php?id=488 Дистанционная подготовка {{---}} Наибольшая возрастающая подпоследовательность (НВП, Longest Increasing Subsequence, LIS)]
 +
* [http://e-maxx.ru/algo/longest_increasing_subseq_log#7 MAXimal :: algo :: Длиннейшая возрастающая подпоследовательность за O (N log N)]
 +
 
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Динамическое программирование]]

Текущая версия на 19:35, 4 сентября 2022

Задача:
Дан массив из [math]n[/math] чисел: [math]a[0..n - 1][/math]. Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.


Определение:
Наибольшая возрастающая подпоследовательность (НВП) (англ. Longest increasing subsequence, LIS) строки [math] x [/math] длины [math] n [/math] — это последовательность [math] x[i_1] \lt x[i_2] \lt \dots \lt x[i_k] [/math] символов строки [math] x [/math] таких, что [math] i_1 \lt i_2 \lt \dots \lt i_k, 1 \leqslant i_j \leqslant n [/math], причем [math] k [/math] — наибольшее из возможных.


Решение за время O(N2)

Построим массив [math]d[/math], где [math]d[i][/math] — это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом [math]i[/math]. Массив будем заполнять постепенно — сначала [math]d[0][/math], потом [math]d[1][/math] и т.д. Ответом на нашу задачу будет максимум из всех элементов массива [math]d[/math]. Заполнение массива будет следующим: если [math]d[i] = 1[/math], то искомая последовательность состоит только из числа [math]a[i][/math]. Если [math]d[i] \gt 1[/math], то перед числом [math]a[i][/math] в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент [math]a[j](j = 0...i - 1)[/math], но такой, что [math]a[j] \lt a[i][/math]. Пусть на каком-то шаге нам надо посчитать очередное [math]d[i][/math]. Все элементы массива [math]d[/math] до него уже посчитаны. Значит наше [math]d[i][/math] мы можем посчитать следующим образом: [math]d[i] = 1 + \max\limits_{j = 0 .. i - 1}{d[j]}[/math] при условии, что [math]a[j] \lt a[i][/math].

Пока что мы нашли лишь максимальную длину наибольшей возрастающей подпоследовательности, но саму ее мы вывести не можем. Для восстановления ответа заведем массив [math]prev[0...n - 1][/math], где [math]prev[i][/math] будет означать индекс в массиве [math]a[][/math], при котором достигалось наибольшее значение [math]d[i][/math]. Для вывода ответа будем идти от элемента с максимальным значениям [math]d[i][/math] по его предкам.

Псевдокод алгоритма

vector<int> findLIS(vector<int> a):
   int n = a.size                     //размер исходной последовательности
   int prev[0..n - 1]
   int d[0..n - 1]
 
   for i = 0 to n - 1
       d[i] = 1
       prev[i] = -1
       for j = 0 to i - 1
           if (a[j] < a[i] and d[j] + 1 > d[i])
               d[i] = d[j] + 1
               prev[i] = j
 
   pos = 0                            // индекс последнего элемента НВП
   length = d[0]                      // длина НВП
   for i = 0 to n - 1
       if d[i] > length
           pos = i
           length = d[i]
   
   // восстановление ответа
   vector<int> answer
   while pos != -1
       answer.push_back(a[pos])
       pos = prev[pos]
   reverse(answer)
 
   return answer    

Решение за O(N log N)

Для более быстрого решения данной задачи построим следующую динамику: пусть [math]d[i](i = 0...n)[/math] — число, на которое оканчивается возрастающая последовательность длины [math]i[/math], а если таких чисел несколько — то наименьшее из них. Изначально мы предполагаем, что [math]d[0] = -\infty[/math], а все остальные элементы [math]d[i] =[/math] [math]\infty[/math]. Заметим два важных свойства этой динамики: [math]d[i - 1] \leqslant d[i][/math], для всех [math]i = 1...n[/math] и каждый элемент [math]a[i][/math] обновляет максимум один элемент [math]d[j][/math]. Это означает, что при обработке очередного [math]a[i][/math], мы можем за [math] O(\log n) [/math] c помощью двоичного поиска в массиве [math]d[/math] найти первое число, которое больше либо равно текущего [math]a[i][/math] и обновить его.

Для восстановления ответа будем поддерживать заполнение двух массивов: [math]pos[/math] и [math]prev[/math]. В [math]pos[i][/math] будем хранить индекс элемента, на который заканчивается оптимальная подпоследовательность длины [math]i[/math], а в [math]prev[i][/math] — позицию предыдущего элемента для [math]a[i][/math].

Псевдокод алгоритма

vector<int> findLIS(vector<int> a):
   int n = a.size                     //размер исходной последовательности
   int d[0..n]
   int pos[0..n]
   int prev[0..n - 1]
   length = 0
   
   pos[0] = -1
   d[0] = -INF
   for i = 1 to n
       d[i] = INF
   for i = 0 to n - 1
       j = binary_search(d, a[i])
       if (d[j - 1] < a[i] and a[i] < d[j])
           d[j] = a[i]
           pos[j] = i
           prev[i] = pos[j - 1]
           length = max(length, j)
   
   // восстановление ответа
   vector<int> answer
   p = pos[length]
   while p != -1
       answer.push_back(a[p])
       p = prev[p]
   reverse(answer)
 
   return answer

Ещё одно решение за О(N log N)

Существует ещё одно решение, которое позволяет нам найти длину наибольшей возрастающей подпоследовательности, но без возможности восстановления данной подпоследовательности. Для этого мы воспользуемся таблом Юнга. Оно обладает таким свойством, что длина первой строки табла и будет являться искомой величиной[1].

Само табло представляет из себя расположение [math]n_1+n_2+...+n_M[/math] различных целых чисел в массиве строк, выровненных по левому краю, где в [math]i[/math] строке содержится [math]n_i[/math] элементов; при этом в каждой строке элементы возрастают слева направо, а элементы каждого столбца возрастают сверху вниз. Чтобы построить табло требуется прочитать очередной элемент [math]a_i[/math], если он больше либо равен [math]n_j[/math], где [math]j[/math] — длина строки, то просто добавить в конец строки, если меньше, то требуется найти первый элемент [math]b[/math], который больше данного [math]a_i[/math]. Поставить элемент [math]a[/math] вместо [math]b[/math]. С элементом [math]b[/math] требуется провести те же действия, что и с [math]a[/math], только уже на [math]i+1[/math] строке табла.

Пример построения табла на массиве [math]a = [ 3, 4, 9, 2, 5, 1 ][/math] :

1. Берём элемент [math]3[/math]. Видим, что [math]3 \gt 0[/math], который расположен на первой строке в ячейке с индексом [math]j = 0[/math]. Увеличиваем [math]j[/math] и [math]t[i][j] = 3[/math].

  3  

2. Берём элемент [math]4[/math]. Видим, что [math]4 \gt 3[/math]. Увеличиваем [math]j[/math] и [math]t[i][j] = 4[/math].

  3     4  

3. Аналогично для элемента [math]9[/math].

  3     4     9  

4. Берём элемент [math]2[/math]. Так как [math]2 \lt 9[/math], то бинарным поиском находим нужную нам позицию [math]z[/math], такую, что [math]t[i][z-1] \leqslant 2 \lt t[i][z][/math]. В данном случае это первая позиция. Присваиваем [math]t[i][z] = 2[/math] и проделываем такую же операцию, но для строки с индексом [math]i+1[/math].

  2     4     9  
  3  

5. Аналогично для элемента [math]5[/math].

  2     4     5  
  3     9  

6. Аналогично для элемента [math]1[/math].

  1     4     5  
  2     9  
  3  

Таким образом, длина наибольшей возрастающей подпоследовательности для массива [math]a[/math] равна [math]3[/math] (например, подпоследовательность из элементов [math][ 3, 4, 9 ][/math]).


См. также

Примечания

Источники информации