Войти Регистрация
Алгоритмы

49. Сумма минимумов всех подотрезков

Сложная

Дан массив положительных чисел arr. Для каждого непрерывного подотрезка возьмите его минимум и сложите все эти минимумы.

Верните сумму по модулю 10⁹ + 7.

В работе: Суммарная «узкая» пропускная способность по всем отрезкам маршрута.

Пример 1

Ввод
arr = [2, 4, 1]
Вывод
11

[2]=2, [4]=4, [1]=1, [2,4]=2, [4,1]=1, [2,4,1]=1 — итого 11.

Пример 2

Ввод
arr = [5]
Вывод
5

Ограничения

  • 1 ≤ длина arr ≤ 3·10⁴
  • 1 ≤ arr[i] ≤ 3·10⁴
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def sum_subarray_mins(arr):
Монотонный стекВклад элементацельO(n)

Источник: тег Авито на LeetCode, 2025. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.