Условие допустимости,
расширение и сжатие

Категория

Алгоритм

Уровень

Начальный

Опирается на

Главы 10.1 и 10.2; глава 9.5: цикл while для левой границы

Зачем это знать

На этой схеме построены обе задачи КТП занятия 10

§1Задача: самый длинный отрезок в пределах лимита

Задачи КТП разобраны в главах 10.4 и 10.5. Здесь — задача, на которой схема прохода видна без дополнительных деталей. Состояние окна в ней — одно число, сумма, как в модуле 9. Ответ — одно число, длина. Задача уже встречалась в тренажёре главы 10.2: расходы по дням и бюджет.

Условие допустимости здесь — total <= limit. Числа неотрицательные, поэтому расширение окна сумму не уменьшает, а сжатие не увеличивает. Это требование из главы 10.2, без него схема не работает.

§2Решение перебором

Самое прямое решение — проверить все отрезки. Внешний цикл выбирает начало отрезка l, внутренний двигает конец r от l до конца списка. Сумма отрезка накапливается в total: при каждом сдвиге r к ней прибавляется один элемент. Если сумма не больше лимита, длина отрезка сравнивается с лучшей. Это решение пишется сразу и служит эталоном: с ним сравнивают быстрое.

def longest_within_brute(nums, limit):
    if limit < 0:
        raise ValueError("limit должно быть не меньше 0")
    best = 0
    for l in range(len(nums)):
        total = 0
        for r in range(l, len(nums)):
            total += nums[r]
            if total <= limit:
                best = max(best, r - l + 1)
    return best

>>> best = 3
>>> r, l = 6, 3
>>> r - l + 1
4
>>> best = max(best, r - l + 1)
>>> best
4
>>> max(4, 0)
4

Прогон ниже сделан на первых четырёх числах примера, чтобы он не был слишком длинным: в списке из четырёх элементов 10 отрезков, в списке из восьми — 36. Голубые ячейки — текущий отрезок с l по r.

На шагах 15 и 18 видно лишнюю работу. Отрезок nums[0:3] с суммой 11 уже больше лимита, а перебор всё равно проверяет nums[0:4] с суммой 12. На шаге 21 видно вторую потерю: при переходе к l = 1 сумма сбрасывается в ноль и набирается заново. При этом сумма nums[1:3] отличается от уже посчитанной суммы nums[0:3] на один элемент.

§3Сколько стоит перебор

Отрезков с началом 0 в списке n штук, с началом 1 — на один меньше, с началом n − 1 — один. Всего n + (n − 1) + … + 1 = n·(n + 1)/2. На каждый отрезок перебор тратит одно сложение и одно сравнение, поэтому время — O(n²).

Перебор можно ускорить оператором break: выйти из внутреннего цикла, как только сумма превысила лимит. На списке, где все отрезки допустимы, например из одних нулей, break не сработает ни разу, и проверок останется столько же. Поэтому оценка в худшем случае та же, O(n²). Третий столбец таблицы — число шагов окна, оно получено в §5.

§4Схема прохода

Обе потери перебора убирает одна идея: при переходе к следующему отрезку менять сумму на один элемент и не проверять отрезки, про которые ответ уже известен. Сравнение из жизни: покупатель идёт вдоль полки и кладёт в корзину каждый следующий товар. Если сумма превысила деньги в кошельке, он выкладывает товары, взятые раньше всех, пока сумма снова не уложится. Корзину заново он не собирает и к пройденной части полки не возвращается.

В коде корзина — окно, сумма покупок — total, кошелёк — limit. На каждом шаге внешнего цикла выполняются три действия.

1. Расширение. Правая граница r сдвигается на один элемент, он добавляется в состояние окна: total += nums[r].
2. Сжатие. Пока условие допустимости нарушено, то есть пока total > limit, самый левый элемент убирается из состояния окна. Затем левая граница сдвигается: total -= nums[l], l += 1.
3. Запись. После сжатия окно допустимо. Его длина r − l + 1 сравнивается с лучшей.

окно [4, 2], сумма 6             допустимо, длина 2
расширение: пришло 5             окно [4, 2, 5], сумма 11 > 7
сжатие: ушло 4                   окно [2, 5], сумма 7 ≤ 7, цикл while закончен
запись: длина 2                  best = max(2, 2) = 2

В этой схеме r — индекс последнего элемента окна, как в главе 9.5. Поэтому в окно входят элементы с l по r включительно, и длина окна — r − l + 1. В главе 10.1 окно записано полуинтервалом [l, r) с длиной r − l. Это две записи одного и того же окна: правая граница полуинтервала на единицу больше индекса последнего элемента.

>>> total = 14
>>> l = 3
>>> nums = [4, 2, 5, 1, 1, 2, 1, 9]
>>> while total > 7:
...     total -= nums[l]
...     l += 1
...     print(l, total)
...
4 13
5 12
6 10
7 9
8 0

В выводе видно, что окно может стать пустым: l = 8 стоит правее r = 7, сумма равна 0, длина r − l + 1 равна 0. Так происходит, когда один элемент больше лимита. Отдельной проверки для этого случая не нужно: сумма пустого окна равна 0, лимит не меньше 0, поэтому цикл останавливается раньше, чем l выйдет за границу списка.

§5Почему левая граница не возвращается назад

Перебор для каждого конца отрезка проверяет все начала. Окно этого не делает: после сдвига правой границы левая остаётся там, где была, или уходит вправо. Нужно убедиться, что при этом не пропущен ни один отрезок, который мог быть ответом.

Рассуждение на числах примера. При r = 2 окно nums[0:3] = [4, 2, 5] имеет сумму 11, и левая граница сдвигается на 1. Затем правая граница переходит на r = 3. Отрезок с началом 0 и концом 3 — это [4, 2, 5, 1]. Он содержит отрезок [4, 2, 5] целиком и ещё один элемент. Числа неотрицательные, поэтому его сумма не меньше 11 и тоже больше лимита. Проверять его не нужно, и возвращать левую границу в 0 незачем.

Из правила получается оценка времени. Правая граница сдвигается n раз: по одному разу на каждый повтор цикла for. Левая граница двигается только вправо и не обгоняет правую больше чем на одну позицию, поэтому за весь проход она сдвигается не больше n раз. Всего сдвигов не больше 2·n, каждый стоит одно сложение или вычитание.

§6Расширение и сжатие вручную

Прежде чем смотреть код, сделайте проход сами на другом списке. На каждом шаге выберите, какую границу сдвинуть. Длина допустимого окна сравнивается с лучшей автоматически. Неверный ход не выполняется, вместо него появляется объяснение.

§7Сборка цикла из строк

Начало функции уже написано: проверка limit и три переменные — best = 0, total = 0, l = 0. Ниже семь строк, из которых состоит остальная часть: цикл с расширением, сжатием и записью и возврат ответа. Расставьте их по порядку. Готовая функция — в §8.

Напишите функцию сами в окне ниже, прямо на странице. «Запустить тесты» проверяет её на десяти тестах. Среди них сумма точно на лимите, элемент больше лимита, пустой список, неверный лимит и сравнение с перебором на двухстах случайных списках. Часть тестов заготовка проходит сразу. Первый запуск загружает Python в браузер, около 10 МБ.

§8Код и пошаговый прогон

def longest_within(nums, limit):
    if limit < 0:
        raise ValueError("limit должно быть не меньше 0")
    best = 0
    total = 0
    l = 0
    for r in range(len(nums)):
        total += nums[r]
        while total > limit:
            total -= nums[l]
            l += 1
        best = max(best, r - l + 1)
    return best

Прогон на примере из §1. Голубые ячейки — окно с l по r, бледные — элементы, которые из окна ушли. В прогоне стоит проследить за тремя местами. На шагах 15–18 одно сжатие возвращает окно в лимит. На шагах 44–59 после прихода числа 9 цикл while выполняется пять раз подряд, и окно становится пустым. На шаге 41 записывается ответ — длина 4.

Это ответ на контрольный вопрос занятия из КТП: «Какой инвариант остаётся истинным после каждого перемещения границы?» Для окна переменного размера он состоит из двух частей: состояние окна соответствует его границам, и после сжатия окно допустимо.

§9Две ошибки в порядке строк

В КТП типичная ошибка занятия названа так: «неверное обновление состояния до или после сдвига границы». В обеих версиях ниже строки те же, что в верной функции, изменён только их порядок. Каждая запущена на примере из §1, и её можно пройти по шагам. Верный ответ — 4.

Верная версия — прогон в §8. Обе ошибки находят тесты песочницы test_example, test_no_window, test_zeros и сравнение с перебором, вторую — ещё и test_big_element. Порядок строк в теле цикла запоминают по смыслу: элемент сначала убирают из состояния окна и только после этого сдвигают границу, иначе индекс l уже показывает на другой элемент.

§10Проверьте себя