Решение задачи

Алгоритм решения задачи:

dp(i, j) показывает, может ли s(i... j) образовывать палиндромную подстроку, dp(i, j) истинно, когда s(i) равно s(j) и s(i+1... j-1) является палиндромной подстрокой. Когда мы нашли палиндром, проверьте, самый ли он длинный. Временная сложность O(n^2).

Небольшое пояснение, почему индексы в циклах for выставляются именно такими:

j всегда должно быть больше или равно i. Почему? i — начальный индекс подстроки, j — конечный индекс подстроки. Не имеет смысла, чтобы i было больше, чем j. Визуализация помогает мне, поэтому, если вы визуализируете массив dp 2d, подумайте о диагонали, которая проходит сверху слева вниз справа. Мы заполняем только верхнюю правую половину dp.

Почему мы считаем вниз для i, но считаем вверх для j? Каждая подзадача dp[i][j] зависит от dp[i+1][j-1] (dp[i+1][j-1] должно быть истинным, а s.charAt(i) должно равняться s. charAt(j) для истинности dp[i][j]).