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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение за время O(N2))
(была ошибка)
(не показано 37 промежуточных версий 5 участников)
Строка 1: Строка 1:
Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).''
+
{{Шаблон: Задача
 +
|definition =
 +
Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).''}}
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Наибольшая общая возрастающая подпоследовательность (НОВП)''' (''англ''. longest common increasing subsequence - LCIS)  массива <tex> A </tex> длины <tex> n </tex> и массива <tex> B </tex> длины <tex> m </tex> — это последовательность <tex> X = \left \langle x_1, x_2, ..., x_k \right \rangle </tex> такая, что <tex> x_1 < x_2 < \dots < x_k </tex>, <tex> X </tex> является ''подпоследовательностью'' <tex> A </tex> и <tex> B </tex> }}
+
'''Наибольшая общая возрастающая подпоследовательность, НОВП''' (англ. ''longest common increasing subsequence, LCIS'')  массива <tex> A </tex> длины <tex> n </tex> и массива <tex> B </tex> длины <tex> m </tex> — это последовательность <tex> X = \left \langle x_1, x_2, \ldots, x_k \right \rangle </tex> такая, что <tex> x_1 < x_2 < \ldots < x_k </tex>, <tex> X </tex> является ''подпоследовательностью'' <tex> A </tex> и <tex> B </tex>. }}
  
==Решение за время O(N<sup>4</sup>)==
+
==Решение за время O(n<sup>2</sup> &#215; m<sup>2</sup>)==
Построим следующую динамику: <tex> d[i][j] </tex> - это длина наибольшей возрастающей подпоследовательности массивов <tex> a </tex> и <tex> b </tex>, последний элемент которой <tex> a[i] </tex> и <tex> b[j] (a[i] = b[j]) </tex>. Будем заполнять <tex> d[i][j] </tex> сначала по увеличению <tex> i </tex>, а при равенстве по увеличению <tex> j </tex>. Ответом на задачу будет максимум из всех элементов <tex> d[i][j] </tex> (где <tex> i = 1...n </tex>, <tex> j = 1...m. </tex>)
+
Построим следующую динамику: <tex> d[i][j] </tex> {{---}} это длина наибольшей возрастающей подпоследовательности массивов <tex> a </tex> и <tex> b </tex>, последний элемент которой <tex> a[i] </tex> и <tex> b[j] (a[i] = b[j]) </tex>. Будем заполнять <tex> d[i][j] </tex> сначала по увеличению <tex> i </tex>, а при равенстве по увеличению <tex> j </tex>. Ответом на задачу будет максимум из всех элементов <tex> d[i][j] </tex> (где <tex> i = 1...n </tex>, <tex> j = 1...m. </tex>)
  
 
Заполнять <tex> d </tex> будем следующим образом: на очередном шаге сравниваем элементы <tex> a[i] </tex> и <tex> b[j] </tex>:
 
Заполнять <tex> d </tex> будем следующим образом: на очередном шаге сравниваем элементы <tex> a[i] </tex> и <tex> b[j] </tex>:
 
*Если <tex> a[i] \neq b[j] </tex>, то <tex> d[i][j] = 0 </tex> (так как нет НОВП, оканчивающейся в разных элементах).
 
*Если <tex> a[i] \neq b[j] </tex>, то <tex> d[i][j] = 0 </tex> (так как нет НОВП, оканчивающейся в разных элементах).
*Если <tex> a[i] = b[j] </tex>, то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах <tex> a </tex> и <tex> b </tex>. Заметим, что предыдущие значения <tex> d </tex> уже известны, тогда очередное значение <tex> d[i][j] = max(d[k][l] + 1, </tex> для всех <tex> k = 1..i-1 </tex> и <tex> l = 1..j-1, </tex> при условии, что <tex> a[k] = b[l]) </tex>
+
*Если <tex> a[i] = b[j] </tex>, то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах <tex> a </tex> и <tex> b </tex>. Заметим, что предыдущие значения <tex> d </tex> уже известны, тогда очередное значение <tex dpi="130"> d[i][j] = \max\limits_{k = 1..i-1 \atop l = 1..j-1} d[k][l] + 1 </tex> при условии, что <tex> a[k] = b[l]. </tex>
  
Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> - индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.
+
Длина НОВП будет в элементе с максимальным значением <tex> d[i][j] </tex>. Для восстановления подпоследовательности можно хранить массив предков <tex> prev[1..n] </tex> массива <tex> a: prev[i] </tex> {{---}} индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.
  
  vector<int> '''LCIS'''(vector<int> a, vector<int> b)
+
  '''vector<int>''' LCIS(a: '''int[n]''', b: '''int[m]''')
  d = int[n][m] // динамика
+
   '''for''' i = 1 '''to''' n  
  prev = int[n] // массив предков
+
     '''for''' j = 1 '''to''' m
   '''for''' i = 1...n  
 
     '''for''' j = 1...m
 
 
       '''if''' a[i] == b[j]
 
       '''if''' a[i] == b[j]
         d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
+
         d[i][j] = 1 <font color=green> // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j] </font>
          '''for''' k = 1...i-1
+
        '''for''' k = 1 '''to''' i - 1
            '''for''' l = 1...j-1
+
          '''for''' l = 1 '''to''' j - 1
              '''if''' a[k] == b[l] '''and''' a[k] < a[i] '''and''' d[i][j] < d[k][l] + 1
+
            '''if''' a[k] == b[l] '''and''' a[k] < a[i] '''and''' d[i][j] < d[k][l] + 1
                d[i][j] = d[k][l] + 1
+
              d[i][j] = d[k][l] + 1
                prev[i] = k
+
              prev[i] = k
   // восстановление
+
   <font color=green>// восстановление</font>
   b_i = 1         // ищем лучшую пару (b_i, b_j)
+
   b_i = 1
   b_j = 1         // d[b_i][b_j] <tex> \rightarrow </tex> max
+
   b_j = 1
   '''for''' i = 1...n
+
   '''for''' i = 1 '''to''' n
     '''for''' j = 1...m  
+
     '''for''' j = 1 '''to''' m  
 
       '''if''' d[b_i][b_j] < d[i][j]
 
       '''if''' d[b_i][b_j] < d[i][j]
 
         b_i = i
 
         b_i = i
 
         b_j = j
 
         b_j = j
   vector<int> answer
+
   pos = b_i
   pos = b_i        // проходим по массиву a, выписывая элементы НОВП
+
   <font color=green>// проходим по массиву a, выписывая элементы НОВП</font>
   '''while''' pos != 0
+
  answer: '''vector<int>'''
     answer.push(a[pos])
+
   '''while''' pos <tex> \neq </tex> 0
 +
     answer.pushBack(a[pos])
 
     pos = prev[pos]
 
     pos = prev[pos]
 
   '''return''' answer
 
   '''return''' answer
  
==Решение за время O(N<sup>3</sup>)==
+
==Решение за время O(n<sup>2</sup> &#215; m)==
Улучшим предыдущее решение. Пусть теперь <tex> d[i][j] </tex> - динамика, в которой элемент <tex> a[i] </tex> по-прежнему последний представитель НОВП массива <tex> a </tex>, а <tex> b[j] </tex> может не быть быть последним представителем массива <tex> b </tex>. Тогда если <tex> a[i] \neq b[j] </tex>, будем "протаскивать" последнее удачное сравнение в динамике: <tex> d[i][j] = d[i][j-1] </tex> (понять это можно так: <tex> a[i] \neq b[j] </tex> , поэтому <tex> b[j] </tex> не последний представитель НОВП из массива <tex> b </tex>, а значит предыдущий элемент НОВП находится в префиксе <tex> b[1..j-1] </tex>, но <tex> d[i][j-1] </tex> уже посчитан).
+
Улучшим предыдущее решение. Пусть теперь <tex> d[i][j] </tex> {{---}} динамика, в которой элемент <tex> a[i] </tex> по-прежнему последний представитель НОВП массива <tex> a </tex>, а <tex> b[j] </tex> может не быть быть последним представителем массива <tex> b </tex>:
Если <tex> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </tex> - максимальна.
+
*Если <tex> a[i] \neq b[j] </tex>, будем "протаскивать" последнее удачное сравнение в динамике: <tex> d[i][j] = d[i][j-1] </tex> (понять это можно так: <tex> a[i] \neq b[j] </tex> , поэтому <tex> b[j] </tex> не последний представитель НОВП из массива <tex> b </tex>, а значит предыдущий элемент НОВП находится в префиксе <tex> b[1..j-1] </tex>, но <tex> d[i][j-1] </tex> уже посчитан).
 +
*Если <tex> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </tex> {{---}} максимальна.
 +
 
 +
<tex dpi="120"> d[i][j] = \max\limits_{k = 1..i-1} d[k][j] + 1 </tex> при условии, что <tex> a[k] < a[i].</tex>
  
<tex> d[i][j] = max(d[k][j]) + 1 </tex> для всех <tex> k = 1..i-1, a[k] < a[i]). </tex>
+
Длина НОВП будет в элементе с максимальным значением <tex> d[i][m] </tex>. Для восстановления ответа будем хранить массив предков по массиву <tex> a </tex>, как и в предыдущем решении.
  
  vector<int> '''LCIS'''(vector<int> a, vector<int> b)
+
  '''vector<int>''' LCIS(a: '''int[n]''', b: '''int[m]''')
  d = int[n][m] // динамика
+
   '''for''' i = 1 '''to''' n  
  prev = int[n] // массив предков
+
     '''for''' j = 1 '''to''' m
   '''for''' i = 1...n  
 
     '''for''' j = 1...m
 
 
       '''if''' a[i] == b[j]
 
       '''if''' a[i] == b[j]
         d[i][j] = 1   // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
+
         d[i][j] = 1 <font color=green>// НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]</font>
          '''for''' k = 1...i-1
+
        '''for''' k = 1 '''to''' i - 1
            '''if''' a[k] < a[i] '''and''' d[i][j] < d[k][j] + 1
+
          '''if''' a[k] < a[i] '''and''' d[i][j] < d[k][j] + 1
              d[i][j] = d[k][j] + 1
+
            d[i][j] = d[k][j] + 1
              prev[i] = k
+
            prev[i] = k
 
       '''else'''
 
       '''else'''
         d[i][j] = d[i][j-1]  
+
         d[i][j] = d[i][j - 1]  
   // восстановление
+
   <font color=green>// восстановление</font>
   b_i = 1         // ищем лучший элемент d[b_i][m] <tex> \rightarrow </tex> max
+
   pos = 1 <font color=green>// ищем элемент c максимальным d[pos][m]</font>
   '''for''' i = 1...n
+
   '''for''' i = 1 '''to''' n
     '''if''' d[b_i][m] < d[i][m]
+
     '''if''' d[pos][m] < d[i][m]
       b_i = i
+
       pos = i
   vector<int> answer
+
   <font color=green>// проходим по массиву a, выписывая элементы НОВП</font>
  pos = b_i        // проходим по массиву a, выписывая элементы НОВП
+
  answer: '''vector<int>'''
   '''while''' pos != 0
+
   '''while''' pos <tex> \neq </tex> 0
     answer.push(a[pos])
+
     answer.pushBack(a[pos])
 
     pos = prev[pos]
 
     pos = prev[pos]
 
   '''return''' answer
 
   '''return''' answer
  
==Решение за время O(N<sup>2</sup>)==
+
==Решение за время O(n &#215; m)==
Пусть теперь <tex> d[i][j] </tex> - это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex> (элементы <tex> a[i] </tex> и <tex> b[j] </tex> могут не входить в НОВП). Вычислять <tex> d </tex> будем по увеличению <tex> i </tex>, а при равенстве - по увеличению <tex> j </tex>. Заметим, что в предыдущем решении при каждом равенстве элементов <tex> a[i] </tex> и <tex> b[j] </tex> приходилось пробегать дополнительным циклом по массиву <tex> a </tex> в поисках элемента, меньшего <tex> a[i] </tex>, для которого <tex> d[k][j] </tex> на префиксе <tex> a[1..k] </tex> и <tex> b[1..j] </tex> была наилучшей. А раз мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex> , то <tex> a[i] </tex> можно считать фиксированным, а <tex> b[j] </tex> - переменным. Тогда давайте в дополнительной переменной хранить лучший элемент и его индекс в массиве <tex> b </tex>, такой, что этот элемент строго меньше <tex> a[i] </tex> и значение динамики для него максимально. Фактически, это решение отличается от предыдущих только более "хитрой" реализацией.
+
Модифицируем предыдущее решение, добавив небольшую ''хитрость''. Теперь <tex> d[i][j] </tex> {{---}} это длина наибольшей общей возрастающей подпоследовательности префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, причем элемент <tex> b[j] </tex> {{---}} последний представитель НОВП массива <tex> b </tex>, а <tex> a[i] </tex> может не быть последним в массиве <tex> a </tex>. Вычислять <tex> d </tex> будем всё так же: сначала по увеличению <tex> i </tex>, а при равенстве {{---}} по увеличению <tex> j </tex>. Тогда для очередного значения <tex> d[i][j] </tex> есть два варианта:
 
+
*<tex> a[i] </tex> не входит в НОВП. Тогда <tex> d[i][j] = d[i-1][j] </tex>: значение динамики уже посчитано на префиксе <tex> a[1..i-1] </tex>.
  vector<int> '''LCIS'''(vector<int> a, vector<int> b)
+
*<tex> a[i] </tex> входит в НОВП. Это значит, что <tex> a[i] = b[j] </tex>, то есть для подсчёта <tex> d[i][j] </tex> нужно пробегать циклом по <tex> b </tex> в поисках элемента <tex> b[k] < b[j] </tex> с наибольшим значением <tex> d[i-1][k] </tex>. Но мы считаем <tex> d </tex> сначала по увеличению <tex> i </tex>, поэтому будем считать <tex> a[i] </tex> ''фиксированным''. Чтобы не запускать цикл при каждом равенстве <tex> a[i] </tex> элементу <tex> b[k] </tex>, в дополнительной переменной <tex> best </tex> будем хранить "лучший" элемент (и его индекс <tex> ind </tex> в массиве <tex> b </tex>) такой, что этот элемент строго меньше <tex> a[i] </tex> (а также меньше <tex> b[k] </tex>) и значение динамики для него максимально: <tex> b[ind] < a[i] = b[j] </tex> и <tex> best = d[i-1][ind] \rightarrow max. </tex>
  d = int[n][m] // динамика
+
  prev = int[n] // массив предков
+
  '''vector<int>''' LCIS(a: '''int[n]''', b: '''int[m]''')
   '''for''' i = 1...n
+
   '''for''' i = 1 '''to''' n
     best_ind = 0 //позиция "лучшего" элемента в массиве b
+
     ind = 0 <font color=green>// позиция "лучшего" элемента в массиве b</font>
     best = 0     //значение динамики для "лучшего" элемента
+
     best = 0 <font color=green>// значение динамики для "лучшего" элемента</font>
     '''for''' j = 1...m
+
     '''for''' j = 1 '''to''' m
       d[i][j] = d[i-1][j]                           // НОВП на префиксе a[1..i-1] и b[1..j], то есть без элемента a[i]
+
       d[i][j] = d[i - 1][j] <font color=green>// НОВП на a[1..i - 1] и b[1..j] (без элемента a[i])</font>
        '''if''' a[i] == b[j] '''and''' d[i-1][j] < best + 1       // можем использовать a[i]-тый элемент для увеличения НОВП
+
      '''if''' a[i] == b[j] '''and''' d[i - 1][j] < best + 1 <font color=green>// используем a[i]-й элемент для увеличения НОВП</font>
          d[i][j] = best + 1                         
+
        d[i][j] = best + 1                         
          p[j] = best_ind                            
+
        prev[j] = ind                            
        '''if''' a[i] > b[j] '''and''' d[i-1][j] > best // в момент следующего равенства a[i] = b[j'] нам не придётся бежать циклом в поисках элемента k:
+
      '''if''' a[i] > b[j] '''and''' d[i - 1][j] > best <font color=green>// при следующем равенстве a[i] == b[j']</font>
          best = d[i-1][j]                 // b[k] < b[j'] = a[i]. Мы считаем элемент a[i] фиксированным и сравниваем кандидатов с ним
+
        best = d[i - 1][j] <font color=green>// в best будет храниться "лучший" элемент</font>       
          best_ind = j
+
        ind = j <font color=green>// b[ind] < b[j'] и d[i-1][ind] <tex> \rightarrow </tex> max</font>
  // восстановление (по массиву b)
+
  <font color=green>// восстановление (по массиву b)</font>
   b_j = 1 // ищем лучший элемент d[n][b_j]<tex> \rightarrow </tex> max
+
   pos = 1 <font color=green>// ищем лучший элемент d[n][pos] <tex> \rightarrow </tex> max</font>
   '''for''' k = 1...m
+
   '''for''' j = 1 '''to''' m
     '''if''' d[n][b_j] < d[n][j]
+
     '''if''' d[n][pos] < d[n][j]
       b_j = j
+
       pos = j
   vector<int> answer
+
   <font color=green>// проходим по массиву b, выписывая элементы НОВП</font>
  pos = b_j //проходим по массиву b, выписывая элементы НОВП
+
  answer: '''vector<int>'''
   '''while''' pos != 0
+
   '''while''' pos <tex> \neq </tex> 0
     answer.push(b[pos])
+
     answer.pushBack(b[pos])
 
     pos = prev[pos]
 
     pos = prev[pos]
 
   '''return''' answer
 
   '''return''' answer
 +
 +
=== Доказательство оптимальности ===
 +
В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев <tex> a[i] = b[j] </tex> не влияет на корректность алгоритма {{---}} это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения <tex> d[i][j] </tex> мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям.
 +
Напомним, как обозначается динамика: <tex> d[i][j] </tex> {{---}} это НОВП на префиксах <tex> a[1..i] </tex> и <tex> b[1..j] </tex>, где последним элементом НОВП является элемент <tex> b[j] </tex>, а <tex> a[i] </tex> может не быть равен <tex> b[j] </tex> (то есть элемент <tex> a[i'] = b[j] </tex> лежит где-то в префиксе <tex> a[1..i] </tex>). Итак, для <tex> d[i][j] </tex> есть два варианта:
 +
* <tex> a[i] \neq b[j] </tex>, тогда <tex> a[i] </tex> не влияет на результат, и последний элемент НОВП <tex> a[i'] = b[j] </tex>  лежит в <tex> a[1..i-1] </tex>.
 +
* <tex> a[i] = b[j] </tex>, тогда <tex> a[i] </tex> и <tex> b[j] </tex> {{---}} последние элементы НОВП префиксов <tex> a[1..i] </tex> и <tex> b[1..j] </tex>: <tex> b[j] </tex> {{---}} по определению динамики, а <tex> a[i] </tex> как элемент, который может стать последним, не ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в префиксе <tex> a[1..i-1] </tex> есть элемент <tex> a[k] = b[j] </tex>, то его можно заменить на элемент <tex> a[i] </tex> без уменьшения длины НОВП. Если же в <tex> a[1..i-1] </tex> такого элемента нет, то <tex> a[i] </tex> {{---}} единственный из возможных вариантов. Итак, <tex> a[i] </tex> и <tex> b[j] </tex> {{---}} последние элементы НОВП. Значит, начало НОВП (<tex> d[i][j] </tex>) лежит в префиксах <tex> a[1..i-1] </tex> и <tex> b[1..j-1] </tex> (значения для которых уже посчитаны). Мы ищем элемент <tex> b[k] < b[j] </tex> с лучшей динамикой <tex> d[i-1][k] </tex>, что удовлетворяет условию возрастания последовательности и автоматически гарантирует, что конец такой НОВП лежит в префиксе <tex> a[1..i-1] </tex>.
  
 
== См. также ==
 
== См. также ==
Строка 105: Строка 113:
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
 
*[[Задача о наибольшей возрастающей подпоследовательности]]
  
== Источники ==
+
== Источники информации ==
  
*http://codeforces.ru/contest/10/problem/D Codeforces - Задача о наибольшей общей возрастающей подпоследовательности
+
* [http://codeforces.ru/contest/10/problem/D Codeforces {{---}} Задача о наибольшей общей возрастающей подпоследовательности]
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Динамическое программирование]]
 
[[Категория:Динамическое программирование]]
 +
[[Категория:Другие задачи динамического программирования]]

Версия 21:09, 10 ноября 2021

Задача:
Даны два массива: [math] a[1..n] [/math] и [math] b[1..m] [/math]. Требуется найти их наибольшую общую возрастающую подпоследовательность (НОВП).


Определение:
Наибольшая общая возрастающая подпоследовательность, НОВП (англ. longest common increasing subsequence, LCIS) массива [math] A [/math] длины [math] n [/math] и массива [math] B [/math] длины [math] m [/math] — это последовательность [math] X = \left \langle x_1, x_2, \ldots, x_k \right \rangle [/math] такая, что [math] x_1 \lt x_2 \lt \ldots \lt x_k [/math], [math] X [/math] является подпоследовательностью [math] A [/math] и [math] B [/math].


Решение за время O(n2 × m2)

Построим следующую динамику: [math] d[i][j] [/math] — это длина наибольшей возрастающей подпоследовательности массивов [math] a [/math] и [math] b [/math], последний элемент которой [math] a[i] [/math] и [math] b[j] (a[i] = b[j]) [/math]. Будем заполнять [math] d[i][j] [/math] сначала по увеличению [math] i [/math], а при равенстве по увеличению [math] j [/math]. Ответом на задачу будет максимум из всех элементов [math] d[i][j] [/math] (где [math] i = 1...n [/math], [math] j = 1...m. [/math])

Заполнять [math] d [/math] будем следующим образом: на очередном шаге сравниваем элементы [math] a[i] [/math] и [math] b[j] [/math]:

  • Если [math] a[i] \neq b[j] [/math], то [math] d[i][j] = 0 [/math] (так как нет НОВП, оканчивающейся в разных элементах).
  • Если [math] a[i] = b[j] [/math], то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах [math] a [/math] и [math] b [/math]. Заметим, что предыдущие значения [math] d [/math] уже известны, тогда очередное значение [math] d[i][j] = \max\limits_{k = 1..i-1 \atop l = 1..j-1} d[k][l] + 1 [/math] при условии, что [math] a[k] = b[l]. [/math]

Длина НОВП будет в элементе с максимальным значением [math] d[i][j] [/math]. Для восстановления подпоследовательности можно хранить массив предков [math] prev[1..n] [/math] массива [math] a: prev[i] [/math] — индекс предыдущего элемента НОВП, которая оканчивается в [math] a[i] [/math].

vector<int> LCIS(a: int[n], b: int[m])
  for i = 1 to n 
    for j = 1 to m
      if a[i] == b[j]
        d[i][j] = 1  // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j] 
        for k = 1 to i - 1
          for l = 1 to j - 1
            if a[k] == b[l] and a[k] < a[i] and d[i][j] < d[k][l] + 1
              d[i][j] = d[k][l] + 1
              prev[i] = k
  // восстановление
  b_i = 1
  b_j = 1
  for i = 1 to n
    for j = 1 to m 
      if d[b_i][b_j] < d[i][j]
        b_i = i
        b_j = j
  pos = b_i 
  // проходим по массиву a, выписывая элементы НОВП
  answer: vector<int>
  while pos [math] \neq [/math] 0
    answer.pushBack(a[pos])
    pos = prev[pos]
  return answer

Решение за время O(n2 × m)

Улучшим предыдущее решение. Пусть теперь [math] d[i][j] [/math] — динамика, в которой элемент [math] a[i] [/math] по-прежнему последний представитель НОВП массива [math] a [/math], а [math] b[j] [/math] может не быть быть последним представителем массива [math] b [/math]:

  • Если [math] a[i] \neq b[j] [/math], будем "протаскивать" последнее удачное сравнение в динамике: [math] d[i][j] = d[i][j-1] [/math] (понять это можно так: [math] a[i] \neq b[j] [/math] , поэтому [math] b[j] [/math] не последний представитель НОВП из массива [math] b [/math], а значит предыдущий элемент НОВП находится в префиксе [math] b[1..j-1] [/math], но [math] d[i][j-1] [/math] уже посчитан).
  • Если [math] a[i] = b[j] [/math], то одним дополнительным циклом пробежим по [math] a [/math] и найдём предыдущий элемент НОВП, оканчивающейся в [math] a[i] [/math] (он меньше [math] a[i] [/math]). Из подходящих элементов выберем тот, для которого [math] d[k][j] [/math] — максимальна.

[math] d[i][j] = \max\limits_{k = 1..i-1} d[k][j] + 1 [/math] при условии, что [math] a[k] \lt a[i].[/math]

Длина НОВП будет в элементе с максимальным значением [math] d[i][m] [/math]. Для восстановления ответа будем хранить массив предков по массиву [math] a [/math], как и в предыдущем решении.

vector<int> LCIS(a: int[n], b: int[m])
  for i = 1 to n 
    for j = 1 to m
      if a[i] == b[j]
        d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
        for k = 1 to i - 1
          if a[k] < a[i] and d[i][j] < d[k][j] + 1
            d[i][j] = d[k][j] + 1
            prev[i] = k
      else
        d[i][j] = d[i][j - 1] 
  // восстановление
  pos = 1 // ищем элемент c максимальным d[pos][m]
  for i = 1 to n
    if d[pos][m] < d[i][m]
      pos = i
  // проходим по массиву a, выписывая элементы НОВП 
  answer: vector<int>
  while pos [math] \neq [/math] 0
    answer.pushBack(a[pos])
    pos = prev[pos]
  return answer

Решение за время O(n × m)

Модифицируем предыдущее решение, добавив небольшую хитрость. Теперь [math] d[i][j] [/math] — это длина наибольшей общей возрастающей подпоследовательности префиксов [math] a[1..i] [/math] и [math] b[1..j] [/math], причем элемент [math] b[j] [/math] — последний представитель НОВП массива [math] b [/math], а [math] a[i] [/math] может не быть последним в массиве [math] a [/math]. Вычислять [math] d [/math] будем всё так же: сначала по увеличению [math] i [/math], а при равенстве — по увеличению [math] j [/math]. Тогда для очередного значения [math] d[i][j] [/math] есть два варианта:

  • [math] a[i] [/math] не входит в НОВП. Тогда [math] d[i][j] = d[i-1][j] [/math]: значение динамики уже посчитано на префиксе [math] a[1..i-1] [/math].
  • [math] a[i] [/math] входит в НОВП. Это значит, что [math] a[i] = b[j] [/math], то есть для подсчёта [math] d[i][j] [/math] нужно пробегать циклом по [math] b [/math] в поисках элемента [math] b[k] \lt b[j] [/math] с наибольшим значением [math] d[i-1][k] [/math]. Но мы считаем [math] d [/math] сначала по увеличению [math] i [/math], поэтому будем считать [math] a[i] [/math] фиксированным. Чтобы не запускать цикл при каждом равенстве [math] a[i] [/math] элементу [math] b[k] [/math], в дополнительной переменной [math] best [/math] будем хранить "лучший" элемент (и его индекс [math] ind [/math] в массиве [math] b [/math]) такой, что этот элемент строго меньше [math] a[i] [/math] (а также меньше [math] b[k] [/math]) и значение динамики для него максимально: [math] b[ind] \lt a[i] = b[j] [/math] и [math] best = d[i-1][ind] \rightarrow max. [/math]
vector<int> LCIS(a: int[n], b: int[m])
  for i = 1 to n
    ind = 0 // позиция "лучшего" элемента в массиве b
    best = 0 // значение динамики для "лучшего" элемента
    for j = 1 to m	
      d[i][j] = d[i - 1][j] // НОВП на a[1..i - 1] и b[1..j] (без элемента a[i])
      if a[i] == b[j] and d[i - 1][j] < best + 1 // используем a[i]-й элемент для увеличения НОВП
        d[i][j] = best + 1                         
        prev[j] = ind                            
      if a[i] > b[j] and d[i - 1][j] > best // при следующем равенстве a[i] == b[j']
        best = d[i - 1][j] // в best будет храниться "лучший" элемент         
        ind = j // b[ind] < b[j'] и d[i-1][ind] [math] \rightarrow [/math] max 
  // восстановление (по массиву b)
  pos = 1 // ищем лучший элемент d[n][pos] [math] \rightarrow [/math] max 
  for j = 1 to m
    if d[n][pos] < d[n][j]
      pos = j
  // проходим по массиву b, выписывая элементы НОВП 
  answer: vector<int>
  while pos [math] \neq [/math] 0
    answer.pushBack(b[pos])
    pos = prev[pos]
  return answer

Доказательство оптимальности

В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев [math] a[i] = b[j] [/math] не влияет на корректность алгоритма — это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения [math] d[i][j] [/math] мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям. Напомним, как обозначается динамика: [math] d[i][j] [/math] — это НОВП на префиксах [math] a[1..i] [/math] и [math] b[1..j] [/math], где последним элементом НОВП является элемент [math] b[j] [/math], а [math] a[i] [/math] может не быть равен [math] b[j] [/math] (то есть элемент [math] a[i'] = b[j] [/math] лежит где-то в префиксе [math] a[1..i] [/math]). Итак, для [math] d[i][j] [/math] есть два варианта:

  • [math] a[i] \neq b[j] [/math], тогда [math] a[i] [/math] не влияет на результат, и последний элемент НОВП [math] a[i'] = b[j] [/math] лежит в [math] a[1..i-1] [/math].
  • [math] a[i] = b[j] [/math], тогда [math] a[i] [/math] и [math] b[j] [/math] — последние элементы НОВП префиксов [math] a[1..i] [/math] и [math] b[1..j] [/math]: [math] b[j] [/math] — по определению динамики, а [math] a[i] [/math] как элемент, который может стать последним, не ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в префиксе [math] a[1..i-1] [/math] есть элемент [math] a[k] = b[j] [/math], то его можно заменить на элемент [math] a[i] [/math] без уменьшения длины НОВП. Если же в [math] a[1..i-1] [/math] такого элемента нет, то [math] a[i] [/math] — единственный из возможных вариантов. Итак, [math] a[i] [/math] и [math] b[j] [/math] — последние элементы НОВП. Значит, начало НОВП ([math] d[i][j] [/math]) лежит в префиксах [math] a[1..i-1] [/math] и [math] b[1..j-1] [/math] (значения для которых уже посчитаны). Мы ищем элемент [math] b[k] \lt b[j] [/math] с лучшей динамикой [math] d[i-1][k] [/math], что удовлетворяет условию возрастания последовательности и автоматически гарантирует, что конец такой НОВП лежит в префиксе [math] a[1..i-1] [/math].

См. также

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