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

Даны два массива: [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] d[i][j] = max(d[k][j]) + 1 [/math] для всех [math] k = 1..i-1, a[k] \lt 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
            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
  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[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] и значение динамики для него максимально. Фактически, это решение отличается от предыдущих только более "хитрой" реализацией.

vector<int> LCIS(vector<int> a, vector<int> b)
  d = int[n][m] // динамика
  prev = int[n] // массив предков 
  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
  vector<int> answer
  pos := b_j //проходим по массиву b, выписывая элементы НОВП
  while pos != 0
      answer.push(b[pos])
      pos = prev[pos]
  return answer

См. также

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

Источники

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