Выбор ответа Senior Скользящее окно обновлено
Окно и отрицательные числа
Вопрос
Найти самый короткий подмассив с суммой не меньше S. Окно переменной длины работает только если...
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: все числа неотрицательные (положительные). Окно опирается на монотонность: расширение не уменьшает сумму, сжатие не увеличивает.
Варианты ответа
- массив предварительно отсортирован
- все числа неотрицательные (положительные)правильный ответ
- S строго больше нуля и целое
- длина массива чётная
Разбор
Окно опирается на монотонность: расширение не уменьшает сумму, сжатие не увеличивает. С отрицательными числами это ломается: сдвиг левой границы может увеличить сумму, и жадное сжатие пропустит ответ. Тогда используют префиксные суммы с монотонной очередью.
- Сортировка не нужна и ломает «подряд идущие».
- Знак S не спасает при отрицательных элементах.
- Чётность длины ни на что не влияет.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Термины по теме
Ещё по теме «Скользящее окно»
- Самая длинная серия единиц с k заменами
- Перестановка как подстрока
- Самая длинная серия после k замен
- Самая длинная подстрока без повторов
- Максимальная сумма окна длины k
- Максимум гласных в окне
- Кратчайший подмассив с суммой ≥ target
- Самая короткая подстрока с k различными