До чого доводять книжки...#216

До чого доводять книжки... (Розбір)

Розпишемо цільову функцію. Для підвідрізка довжини L = r - l + 1 задоволення дорівнює

\sum_{i=l}^{r} a_i - L + 1 = \sum_{i=l}^{r} (a_i - 1) + 1.

Тобто, якщо ввести новий масив b_i = a_i - 1, то задача зводиться до класичної: знайти максимальну суму непорожнього підвідрізка масиву , а потім додати одиницю.

Максимальна сума підвідрізка знаходиться алгоритмом Кадане за один прохід. Ведемо величину — найкращу суму підвідрізка, що закінчується в поточній позиції:

\mathrm{cur} \leftarrow \max(b_i,\; \mathrm{cur} + b_i),

і оновлюємо глобальний максимум значенням .

Важливо, що підвідрізок має бути непорожнім (l \le r), тому ініціалізувати відповідь нулем не можна — інакше на масиві з усіх від'ємних b_i отримаємо неправильну відповідь. Починайте з \mathrm{cur} = b_1 і максимуму, що дорівнює b_1.

Складність — , чого достатньо при n \le 10^6. Сума сягає 10^{15} за модулем, тому потрібен 64-бітний тип.