1632
правки
Изменения
м
rollbackEdits.php mass rollback
''<font color="green">// подсчёт таблиц</font>''
'''int''' LCS(x: '''intvector''', y: '''intvector'''):
m = length(x)
n = length(y)
Заметим, что для вычисления <tex> lcs[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i-1) </tex>-ая строчки матрицы <tex> lcs </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы:
'''int''' LCS2(x: '''intvector''', y: '''intvector'''):
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
Также можно заметить, что от <tex> (i - 1) </tex>-ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:
'''int''' LCS3(x: '''intvector''', y: '''intvector'''):
'''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>''
swap(x, y)
it_max = -1
'''for''' j = 0 '''to''' y.size()
'''if''' f[j] + s[y.size() - (j + 1)] > max max = f[j] + s[y.size() - (j + 1)]
it_max = j
'''if''' f[y.size() - 1] > max
