Техпрогон
ВойтиНачать бесплатно
Выбор ответа Middle Скользящее окно обновлено

Ошибка в обновлении ответа

Вопрос

Функция ищет длину самого длинного подмассива с суммой не больше limit (числа неотрицательные). В чём ошибка?

function longest(arr, limit) {
  let l = 0, sum = 0, best = 0;
  for (let r = 0; r < arr.length; r++) {
    sum += arr[r];
    while (sum > limit) sum -= arr[l++];
    best = Math.max(best, r - l + 1);
  }
  return best;
}

Попробуйте сами

Выберите вариант, и откроется разбор.

Показать ответ и разбор

Коротко

Правильный ответ: Ошибок нет. Расширяем окно, сжимаем, пока сумма больше limit, после сжатия окно [l, r] валидно, и его длина r - l + 1.

Варианты ответа

  1. Ответ надо обновлять до цикла while
  2. Нужно if вместо while при сжатии
  3. Ошибок нетправильный ответ
  4. Нужно r - l вместо r - l + 1

Разбор

Расширяем окно, сжимаем, пока сумма больше limit, после сжатия окно [l, r] валидно, и его длина r - l + 1. Функция корректна.

  • Обновление до сжатия засчитало бы невалидное окно.
  • if сдвинет левый край только на один элемент, а сумма может остаться больше limit: while здесь нужен.
  • Длина отрезка [l, r] включительно равна r - l + 1.

Ответьте сами, а не прочитайте

В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.

Потренироваться бесплатно

Предыдущий вопрос

Окно и отрицательные числа

Следующий вопрос

Почему вложенный while не даёт O(n²)

Урок по теме

Паттерн: Скользящее окно

Термины по теме

Скользящее окно

Ещё по теме «Скользящее окно»

Все вопросы модуля