Нехай ми хочемо замінити елементів з лівої частини на елементів з правої. Відповідь на задачу тоді буде: сума в лівій частині - сума елементів, які ми заміняємо в лівій частині + сума елементів, які ми заміняємо в правій частині. Можна показати, що однією з оптимальних послідовностей операцій буде:
Посунути елементів зліва, які ми збираємося міняти в найправіші позицій лівої частини. Тобто, поставити їх на позиції n - i, n - i + 1, …, n - 1.
Посунути елементів справа, які ми збираємося міняти в найлівіші позицій правої частини. Тобто, поставити їх на позиції , n + 1, …, n + i - 1.
Виконати i \cdot i операцій, щоб свапнути елементи.
Порахуємо динаміку dp1_{i, j} — мінімальна сума елементів в лівій частині, якщо ми зробили ходів, щоб виконати перший крок. Аналогічно порахуємо динаміку dp2_{i, j} — максимальна сума елементів в правій частині, якщо ми зробили ходів, щоб виконати другий крок. Третій крок зробити просто. Таку динаміку можна рахувати за О(n^4).
Об’єднати такі дві динаміки можна за O(n^5), але це повільно. Модифікуємо трохи другу динаміку наступним чином: dp_{i, j} — Нехай ми зробили перший крок і виконуємо другий. Нам треба ще елементів досунути в правій частині та ми зробили вже сумарно кроків. Ми будемо її перераховувати за допомогою . Таку динаміку можна рахувати за O(n^4) і вона зразу покриє перші два кроки. Оскільки нам треба зробити щонайбільше кроків, то треба взяти ще максимум на префіксі.