48
правок
Изменения
Нет описания правки
Доказательство:<br />
# Так <tex>s(i) \neq s(j)</tex>, символы $s(i)$ и $s(j)$ не могут входит в максимальный подпвлиндром одновременно, то есть либо $s(i)$ входят в максимальный подпвлиндром (тогда его длина $d[i, j - 1]$), либо $s(j)$ входи в максимальный подпвлиндром (тогда его длина $d[i + 1, j]$), либо оба не входят в максимальный подпвлиндром (тогда его длина $= d[i, j - 1] = d[i + 1, j]$). <br />
# Данное равенство следует из факта, что выгодно включить в мп максимальный подпвлиндром символы $s(i)$ и $s(j)$.
=== Примеры задач ===
