← Все вопросы
Скользящее окно: как найти максимальную сумму подотрезка длины k?
12
Есть массив чисел и число k. Нужно найти максимальную сумму среди всех подряд идущих отрезков длины k. Делаю двумя циклами — для больших массивов медленно. Как ускорить?
3 ответа
20
✓ Принятый ответ — помог автору
Скользящее окно: считаешь сумму первых k элементов, а потом на каждом шаге сдвигаешь окно — прибавляешь новый элемент справа и вычитаешь выпавший слева. Пересчитывать всю сумму заново не нужно.
def max_window_sum(a, k):
window = sum(a[:k])
best = window
for i in range(k, len(a)):
window += a[i] - a[i - k]
best = max(best, window)
return best
print(max_window_sum([1, 4, 2, 10, 2, 3, 1, 0, 20], 4)) # 24
Сложность O(n) вместо O(n*k). Это базовый приём «sliding window» для задач на подотрезки фиксированной длины.
7
Не пересчитывай сумму с нуля — добавляй один справа, убирай один слева. O(n).
4
Скользящим окном.
Дарк Драгон Можно и через префиксные суммы, но окно проще и без лишнего массива. · 5 месяцев назад
Ваш ответ
Войдите, чтобы ответить на вопрос.
