Изменения
Новая страница: «Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возраст...»
Даны два массива: <tex> a[1..n] </tex> и <tex> b[1..m] </tex>. Требуется найти их ''наибольшую общую возрастающую подпоследовательность (НОВП).''
==Решение за время O(N<sup>4</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 </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] = 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> prev[1..n] </tex> массива <tex> a: prev[i] </tex> - индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.
a[n], b[m]
d[n][m] //динамика
prev[n] //массив предков
inputData(a, n)
inputData(b, m)
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] <tex> \rightarrow </tex> max
for i = 1...n
for j = 1...m
if d[b_i][b_j] < d[i][j]:
b_i := i
b_j := j
print(d[b_i][b_j]) //размер НОВП
pos := b_i //проходим по массиву a, выписывая элементы НОВП
while pos != 0:
print(a[pos])
pos := prev[pos]
==Решение за время O(N<sup>3</sup>)==
Улучшим предыдущее решение. Пусть теперь <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> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a[] </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </tex> - максимальна.
Правильнее было бы использовать индекс <tex> j-1 </tex> в <tex> d[k][j-1] </tex>, то есть без элемента <tex> b[j] </tex>. Но так как последовательность ''строго возрастает'', <tex> b[j] </tex> точно не будет два раза элементом НОВП. Тогда мы, не рассматривая граничные случаи <tex> d[i][0] </tex>, можем использовать индекс <tex> j </tex> в динамике <tex> d[k][j] </tex>.
<tex> d[i][j] = max(d[k][j]) + 1 </tex> для всех <tex> k = 1..i-1, a[k] < a[i]). </tex>
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] <tex> \rightarrow </tex> 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<sup>2</sup>)==
Пусть теперь <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> и значение динамики для него максимально. Фактически, это решение отличается от предыдущих только более "хитрой" реализацией.
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[b_i][m] <tex> \rightarrow </tex> 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]
==Решение за время O(N<sup>4</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 </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] = 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> prev[1..n] </tex> массива <tex> a: prev[i] </tex> - индекс предыдущего элемента НОВП, которая оканчивается в <tex> a[i] </tex>.
a[n], b[m]
d[n][m] //динамика
prev[n] //массив предков
inputData(a, n)
inputData(b, m)
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] <tex> \rightarrow </tex> max
for i = 1...n
for j = 1...m
if d[b_i][b_j] < d[i][j]:
b_i := i
b_j := j
print(d[b_i][b_j]) //размер НОВП
pos := b_i //проходим по массиву a, выписывая элементы НОВП
while pos != 0:
print(a[pos])
pos := prev[pos]
==Решение за время O(N<sup>3</sup>)==
Улучшим предыдущее решение. Пусть теперь <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> a[i] = b[j] </tex>, то одним дополнительным циклом пробежим по <tex> a[] </tex> и найдём предыдущий элемент НОВП, оканчивающейся в <tex> a[i] </tex> (он меньше <tex> a[i] </tex>). Из подходящих элементов выберем тот, для которого <tex> d[k][j] </tex> - максимальна.
Правильнее было бы использовать индекс <tex> j-1 </tex> в <tex> d[k][j-1] </tex>, то есть без элемента <tex> b[j] </tex>. Но так как последовательность ''строго возрастает'', <tex> b[j] </tex> точно не будет два раза элементом НОВП. Тогда мы, не рассматривая граничные случаи <tex> d[i][0] </tex>, можем использовать индекс <tex> j </tex> в динамике <tex> d[k][j] </tex>.
<tex> d[i][j] = max(d[k][j]) + 1 </tex> для всех <tex> k = 1..i-1, a[k] < a[i]). </tex>
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] <tex> \rightarrow </tex> 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<sup>2</sup>)==
Пусть теперь <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> и значение динамики для него максимально. Фактически, это решение отличается от предыдущих только более "хитрой" реализацией.
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[b_i][m] <tex> \rightarrow </tex> 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]
