Джеррі зупиняється, коли їсти далі невигідно, тож для довільного масиву виконано
— за умови, що сума всього кола не додатна, інакше найкращим префіксом може виявитися все коло.
Спробуємо взяти a_i = c_i - c_{i+1} (індекси циклічні). Ці різниці задовольняють рівняння одразу для всіх , але їхня сума дорівнює нулю, а при нульовій сумі рівняння мають цілу сім'ю розв'язків: разом із їм задовольняє і , зменшене на будь-яку сталу до появи нуля. Реальний масив префіксних максимумів — найменший з них, тобто , зменшене на . Тому при \min c = 0 такий масив уже підходить, а при \min c = \mu > 0 відповідь буде зсунута вниз на .
Виправляє це одне число. Нехай — позиція мінімуму . Додамо до елемента a_{m-1} (циклічно). Тепер сума кола дорівнює рівно , отже кожен старт може з'їсти все коло і отримати щонайменше ; для стартів, у яких c_i > \mu, максимум і далі досягається на короткому префіксі й не змінюється, а старт отримує рівно . Саме тому доданок ставиться безпосередньо перед мінімальним стартом: тоді для нього повне коло — єдиний спосіб набрати .
Для прикладу c = [5, 2, 1] маємо \mu = 1 у позиції , різниці дають [3, 1, -4], а після додавання до a_2 — [3, 2, -4].
Складність: .
Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.