Ctrl K

НОД, умноженный на сумму

Сложная
Дан массив положительных чисел values и число min_len. «Вес» непрерывного куска массива — это сумма его элементов, умноженная на их наибольший общий делитель. Верните наибольший вес среди всех непрерывных кусков, в которых не меньше min_len элементов.
Пример 1
values=[3, 6, 6, 2, 9], min_len=2 → 72

Кусок [6, 6]: НОД 6, сумма 12, произведение 72. Кусок [3, 6, 6] даёт лишь 3 · 15 = 45.

Пример 2
values=[5, 1, 8], min_len=1 → 64

Одиночный элемент 8: НОД 8, сумма 8, итог 64.

Пример 3
values=[4, 8, 12, 7], min_len=3 → 96
Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁶
  • 1 ≤ min_len ≤ len(values)
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиk-я сумма марками одного номинала СложнаяНОД пар по номеру в сортировке СложнаяСтесать простыми до возрастания СредняяЧисла с рабочих клавиш СложнаяСамая большая группа с общими делителями Сложная
загружаем Python…
Вход
values=[3, 6, 6, 2, 9], min_len=2
Ожидается
72

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 99 тестов на сервере, включая скрытые.