Ctrl K

Разнообразное окно с лучшей суммой

Средняя
Дан массив положительных чисел values и два числа min_distinct и width. Окно — это отрезок подряд идущих элементов длины ровно width. Окно считается разнообразным, если в нём хотя бы min_distinct различных значений. Верните наибольшую сумму среди разнообразных окон. Если ни одного такого окна нет, верните 0.
Пример 1
values=[4, 4, 9, 1, 9, 9], min_distinct=2, width=3 → 19

Окна: [4, 4, 9] = 17, [4, 9, 1] = 14, [9, 1, 9] = 19, [1, 9, 9] = 19 — во всех хотя бы два разных числа, лучшее 19.

Пример 2
values=[3, 3, 3, 3], min_distinct=2, width=2 → 0

В каждом окне только тройки, ни одно не подходит — ответ 0.

Пример 3
values=[8, 2, 8, 5, 7], min_distinct=3, width=4 → 23

[8, 2, 8, 5] содержит три разных числа и даёт 23, [2, 8, 5, 7] — четыре разных и 22. Ответ 23.

Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ min_distinct ≤ width ≤ len(values)
  • 1 ≤ values[i] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОтрезок плейлиста из двух жанров СредняяОкна с заданным числом тревог СредняяОтрезки с k нечётными СредняяДва отрезка с нужной суммой СредняяСнять с краёв ровно столько Средняя
загружаем Python…
Вход
values=[4, 4, 9, 1, 9, 9], min_distinct=2, width=3
Ожидается
19

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