Розпишемо цільову функцію. Для підвідрізка довжини L = r - l + 1 задоволення дорівнює
Тобто, якщо ввести новий масив b_i = a_i - 1, то задача зводиться до класичної: знайти максимальну суму непорожнього підвідрізка масиву , а потім додати одиницю.
Максимальна сума підвідрізка знаходиться алгоритмом Кадане за один прохід. Ведемо величину — найкращу суму підвідрізка, що закінчується в поточній позиції:
і оновлюємо глобальний максимум значенням .
Важливо, що підвідрізок має бути непорожнім (l \le r), тому ініціалізувати відповідь нулем не можна — інакше на масиві з усіх від'ємних b_i отримаємо неправильну відповідь. Починайте з \mathrm{cur} = b_1 і максимуму, що дорівнює b_1.
Складність — , чого достатньо при n \le 10^6. Сума сягає 10^{15} за модулем, тому потрібен 64-бітний тип.