values длины n. Его *взвешенная сумма* — это 0·a[0] + 1·a[1] + … + (n − 1)·a[n − 1], то есть каждый элемент умножается на свой индекс.
Массив можно циклически сдвинуть на любое число позиций (последний элемент переходит в начало). Найдите наибольшую взвешенную сумму среди всех n циклических сдвигов values, включая сам исходный массив.
Перебор всех сдвигов занимает O(n²) — попробуйте найти решение за O(n).values=[2, 0, 5] → 10
Сдвиги массива: [2, 0, 5] даёт 0·2 + 1·0 + 2·5 = 10, [5, 2, 0] даёт 2, [0, 5, 2] даёт 9. Максимум — 10.
values=[-3, 7] → 7
[-3, 7] даёт 7, [7, -3] даёт -3.
values=[42] → 0
Единственный элемент стоит на позиции 0 и умножается на ноль.
values=[2, 0, 5]
10
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 83 теста на сервере, включая скрытые.