Ctrl K

Разброс по всем наборам

Сложная
Разброс набора чисел — это разность между его наибольшим и наименьшим элементами. Дан массив values. Рассмотрите все его непустые подпоследовательности — наборы, которые получаются вычёркиванием любых элементов (возможно, ни одного) без изменения порядка остальных. Наборы из одинаковых значений, взятые с разных позиций, считаются разными. Верните сумму разбросов всех таких наборов по модулю 10⁹ + 7.
Пример 1
values=[5, 1, 4] → 12

Наборы из одного элемента дают разброс 0. Пары: {5, 1} → 4, {5, 4} → 1, {1, 4} → 3. Весь массив: 5 − 1 = 4. Итого 4 + 1 + 3 + 4 = 12.

Пример 2
values=[7, 7] → 0

Во всех наборах максимум равен минимуму, поэтому ответ 0.

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

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