Выбор ответа Junior Скользящее окно спрашивают часто обновлено
Максимальная сумма окна длины k
Вопрос
Нужно найти максимальную сумму подмассива ровно из k подряд идущих элементов. Сложность лучшего решения?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: O(n): прибавлять входящий, вычитать выходящий. Окно сдвигается на 1: сумма меняется на +arr[i] - arr[i - k], это O(1) на шаг, O(n) всего. - Пересчёт каждого окна O(n · k). - Сортировка ломает требование «подряд идущих». - O(k) невозможно: надо просмотреть все n элементов.
Варианты ответа
- O(n · k): считать сумму каждого окна заново
- O(n log n): отсортировать и взять k наибольших
- O(k): достаточно первого окна и его соседей
- O(n): прибавлять входящий, вычитать выходящийправильный ответ
Разбор
Окно сдвигается на 1: сумма меняется на +arr[i] - arr[i - k], это O(1) на шаг, O(n) всего.
- Пересчёт каждого окна O(n · k).
- Сортировка ломает требование «подряд идущих».
- O(k) невозможно: надо просмотреть все n элементов.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Термины по теме
Ещё по теме «Скользящее окно»
- Самая длинная серия единиц с k заменами
- Перестановка как подстрока
- Самая длинная серия после k замен
- Самая длинная подстрока без повторов
- Максимальная сумма окна длины k
- Максимум гласных в окне
- Кратчайший подмассив с суммой ≥ target
- Самая короткая подстрока с k различными