Задача о наибольшей общей возрастающей последовательности
| Задача: |
| Даны два массива: и . Требуется найти их наибольшую общую возрастающую подпоследовательность (НОВП). |
| Определение: |
| Наибольшая общая возрастающая подпоследовательность, НОВП (англ. longest common increasing subsequence, LCIS) массива длины и массива длины — это последовательность такая, что , является подпоследовательностью и . |
Решение за время O(n2 × m2)
Построим следующую динамику: — это длина наибольшей возрастающей подпоследовательности массивов и , последний элемент которой и . Будем заполнять сначала по увеличению , а при равенстве по увеличению . Ответом на задачу будет максимум из всех элементов (где , )
Заполнять будем следующим образом: на очередном шаге сравниваем элементы и :
- Если , то (так как нет НОВП, оканчивающейся в разных элементах).
- Если , то эти элементы могут быть частью НОВП. Переберём, какие элементы стояли перед ними в массивах и . Заметим, что предыдущие значения уже известны, тогда очередное значение при условии, что
Длина НОВП будет в элементе с максимальным значением . Для восстановления подпоследовательности можно хранить массив предков массива — индекс предыдущего элемента НОВП, которая оканчивается в .
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 0
answer.pushBack(a[pos])
pos = prev[pos]
return answer
Решение за время O(n2 × m)
Улучшим предыдущее решение. Пусть теперь — динамика, в которой элемент по-прежнему последний представитель НОВП массива , а может не быть быть последним представителем массива :
- Если , будем "протаскивать" последнее удачное сравнение в динамике: (понять это можно так: , поэтому не последний представитель НОВП из массива , а значит предыдущий элемент НОВП находится в префиксе , но уже посчитан).
- Если , то одним дополнительным циклом пробежим по и найдём предыдущий элемент НОВП, оканчивающейся в (он меньше ). Из подходящих элементов выберем тот, для которого — максимальна.
при условии, что
Длина НОВП будет в элементе с максимальным значением . Для восстановления ответа будем хранить массив предков по массиву , как и в предыдущем решении.
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 0
answer.pushBack(a[pos])
pos = prev[pos]
return answer
Решение за время O(n × m)
Модифицируем предыдущее решение, добавив небольшую хитрость. Теперь — это длина наибольшей общей возрастающей подпоследовательности префиксов и , причем элемент — последний представитель НОВП массива , а может не быть последним в массиве . Вычислять будем всё так же: сначала по увеличению , а при равенстве — по увеличению . Тогда для очередного значения есть два варианта:
- не входит в НОВП. Тогда : значение динамики уже посчитано на префиксе .
- входит в НОВП. Это значит, что , то есть для подсчёта нужно пробегать циклом по в поисках элемента с наибольшим значением . Но мы считаем сначала по увеличению , поэтому будем считать фиксированным. Чтобы не запускать цикл при каждом равенстве элементу , в дополнительной переменной будем хранить "лучший" элемент (и его индекс в массиве ) такой, что этот элемент строго меньше (а также меньше ) и значение динамики для него максимально: и
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][ind] max
// восстановление (по массиву b)
pos = 1 // ищем лучший элемент d[n][pos] max
for j = 1 to m
if d[n][pos] < d[n][j]
pos = j
// проходим по массиву b, выписывая элементы НОВП
answer: vector<int>
while pos 0
answer.pushBack(b[pos])
pos = prev[pos]
return answer
Доказательство оптимальности
В данной задаче используется принцип оптимальности на префиксе. Использование дополнительной переменной для подсчета всех случаев не влияет на корректность алгоритма — это всего лишь уловки реализации. Поэтому покажем, что для вычисления очередного значения мы используем оптимальность на подзадачах и обращаемся к уже посчитанным значениям. Напомним, как обозначается динамика: — это НОВП на префиксах и , где последним элементом НОВП является элемент , а может не быть равен (то есть элемент лежит где-то в префиксе ). Итак, для есть два варианта:
- , тогда не влияет на результат, и последний элемент НОВП лежит в .
- , тогда и — последние элементы НОВП префиксов и : — по определению динамики, а как элемент, который может стать последним, не ухудшая результат. Действительно, последовательность строго возрастает, поэтому если в префиксе есть элемент , то его можно заменить на элемент без уменьшения длины НОВП. Если же в такого элемента нет, то — единственный из возможных вариантов. Итак, и — последние элементы НОВП. Значит, начало НОВП () лежит в префиксах и (значения для которых уже посчитаны). Мы ищем элемент с лучшей динамикой , что удовлетворяет условию возрастания последовательности и автоматически гарантирует, что конец такой НОВП лежит в префиксе .
