Природна динаміка тут очевидна: нехай f_i — максимальна кількість балів, з якою можна дістатися позиції . Тоді
а відповідь — f_N. Але прямо це \mathcal{O}(N^2), що завелико.
Рятує те, що літер лише . Розкриємо дужки:
Ключове спостереження: величина |S_i - S_j| залежить не від самих індексів, а лише від пари літер. Тому зафіксуємо пару , де — літера в позиції , а — літера в позиції , і позначимо d[c][\mathit{ch}] = |c - \mathit{ch}|.
Заведемо таблицю
тобто найкращий «внесок» позиції з літерою , якщо ми стрибатимемо в позицію з літерою . Це всього 26 \times 26 чисел.
Тоді перехід стає швидким:
тобто на позицію. Після обчислення f_i оновлюємо таблицю: для кожної літери покладемо
База: f_1 = 0, і для першої позиції одразу заповнюємо відповідні клітинки таблиці; решту ініціалізуємо «мінус нескінченністю», щоб не стрибати з позицій, яких ще не було.
Складність — за часом і \mathcal{O}(26^2) за пам'яттю. Бали сягають порядку N \cdot 25 \cdot N, тобто до 10^{11} і більше, тому рахуйте у 64-бітному типі.