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

Даны два массива: [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, ..., x_k \right \rangle [/math] такая, что [math] x_1 \lt x_2 \lt \dots \lt x_k [/math], [math] X [/math] является подпоследовательностью [math] A [/math] и [math] B [/math]

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

Построим следующую динамику: [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(d[k][l] + 1, [/math] для всех [math] k = 1..i-1 [/math] и [math] l = 1..j-1, [/math] при условии, что [math] a[k] = b[l]) [/math]

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

vector<int> LCIS(vector<int> a, vector<int> b)
d = int[n][m] // динамика
prev = int[n] // массив предков
for i = 1...n 
  for j = 1...m
    if a[i] == b[j]
      d[i][j] = 1 // НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
        for k = 1...i-1
          for l = 1...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_i, b_j)
b_j = 1          // d[b_i][b_j] [math] \rightarrow [/math] max
for i = 1...n
  for j = 1...m 
    if d[b_i][b_j] < d[i][j]
      b_i = i
      b_j = j
vector<int> answer
pos = b_i        // проходим по массиву a, выписывая элементы НОВП
while pos != 0
  answer.push(a[pos])
  pos = prev[pos]
return answer

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

Улучшим предыдущее решение. Пусть теперь [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] j-1 [/math] в [math] d[k][j-1] [/math], то есть без элемента [math] b[j] [/math]. Но так как последовательность строго возрастает, [math] b[j] [/math] точно не будет два раза элементом НОВП. Тогда мы, не рассматривая граничные случаи [math] d[i][0] [/math], можем использовать индекс [math] j [/math] в динамике [math] d[k][j] [/math].

[math] d[i][j] = max(d[k][j]) + 1 [/math] для всех [math] k = 1..i-1, a[k] \lt a[i]). [/math]

for i = 1...n 
   for j = 1...m
      if a[i] == b[j]
         d[i][j] := 1 //НОВП как минимум 1, состоит из одного элемента a[i] <-> b[j]
         for k = 1...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]
//восстановление
b_i := 1         //ищем лучший элемент d[b_i][m] [math] \rightarrow [/math] max
for i = 1...n
   if d[b_i][m] < d[i][m]
      b_i := i
print(d[b_i][m]) //размер НОВП
pos := b_i       //проходим по массиву a, выписывая элементы НОВП
while pos != 0
   print(a[pos])
   pos := prev[pos] 

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

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

d[n][m]
prev[m]
for i = 1...n
   best_ind := 0 //позиция "лучшего" элемента в массиве b
   best := 0     //значение динамики для "лучшего" элемента
   for j = 1...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                         
           p[j] := best_ind                            
       if a[i] > b[j] and d[i-1][j] > best  //в момент следующего равенства a[i] = b[j'] нам не придётся бежать циклом в поисках элемента k:
               best := d[i-1][j]              //b[k] < b[j'] = a[i]. Мы считаем элемент a[i] фиксированным и сравниваем кандидатов с ним
               best_ind := j
//восстановление (по массиву b)
b_j := 1 //ищем лучший элемент d[n][b_j][math] \rightarrow [/math] max
for k = 1...m
   if d[n][b_j] < d[n][j]
      b_j := j
print(d[n][b_j]) //размер НОВП
pos := b_j //проходим по массиву b, выписывая элементы НОВП
while pos != 0
   print(b[pos])
   pos := prev[pos]

См. также

• Задача о наибольшей общей подпоследовательности
• Задача о наибольшей возрастающей подпоследовательности

Источники

• http://codeforces.ru/contest/10/problem/D Codeforces - Задача о наибольшей общей возрастающей подпоследовательности