Возьмем пример

Представьте, что у нас есть следующий массив:

Наша задача:

  • Найдите maxSum подмассива.
  • Подмассив может быть только заданной длины maxSize.

Учитывая приведенный выше массив и maxSize из 2, мы можем сделать вывод, что [0, 3] — это подмассив с наибольшей суммой среди всех других подмассивов.

Если бы нам нужно было придумать решение, основанное на том, как мы решили это только что, мы могли бы:

  • перебирать каждую пару
  • вычислить сумму
  • сохраните сумму + элементы, которые произвели эту сумму, как пару ключ-значение на карте.

Это будет означать, что время, которое потребуется, равно итерации по каждому элементу массива или, другими словами, O(n) . Это не кажется таким уж плохим! Проблема возникает, когда мы смотрим на пространственную сложность. Когда мы создаем пары ключ-значение, мы подвергаемся линейной пространственной сложности. В этой задаче это кажется не таким уж плохим, потому что потенциально у нас есть только 6 пар, но что, если коллекция может состоять из нескольких тысяч или миллионов элементов?

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

Войдите, техника скользящего окна

Это метод динамического программирования для решения проблем, когда мы хотим найти подмассив данных в более крупной коллекции, который удовлетворяет некоторому условию.

Для задач со скользящим окном оптимальные временные и пространственные сложности равны O(n) времени и O(1) пространству. В худшем случае мы перебираем всю коллекцию один раз и не выделяем дополнительное место в памяти относительно элементов коллекции.

Для этого мы создаем подмножество данных (наше окно), а затем расширяем или сжимаем его, пока не удовлетворим нашему условию. Другими словами, как только мы нашли что-то лучшее, мы идем дальше и никогда больше не думаем об утерянной информации.

Используйте это, когда вы видите проблемы, требующие просмотра подстроки или подмассива.

Обратите внимание, что по определению подмножество является непрерывным, что означает, что элементы должны быть смежными друг с другом в коллекции.

Применение скользящего окна

Давайте снова возьмем нашу проблему выше. Учитывая приведенный ниже массив и заданный maxSize = 2 .

Во-первых, давайте запишем требования:

  • Итерация по коллекции (сложность не менее O(n)time).
  • Посмотрите только на maxSize n элементов. Если окно слишком большое, измените размер.
  • Сохраните промежуточную сумму итерируемых элементов в окне как currentSum. Затем сравните с maxSum или наибольшей суммой, рассчитанной до сих пор. Если больше, обновите maxSum .

Изложение наших требований на данный момент может выглядеть так:

В первой и второй итерациях (i = 0иi = 1соответственно) у нас нет проблем, и похоже, что все работает, как и ожидалось. Давайте посмотрим на третью итерацию, где i = 2.

Мы столкнулись с проблемой! Мы отслеживали нашу сумму, делая что-то вроде currentSum += array[i]

В этот момент наше currentSum w/o resizing оказывается равным 2. Размер окна нарушает наше ограничение maxSize, и если мы не исправим его, мы можем неточно сравнивать суммы.

Вы заметили, что я включил индексы массива под значениями? Белая доска помогает нам видеть все части данных, к которым у нас есть доступ, даже те, которые мы не храним в переменной явно! Это ключ!

Некоторые вещи, которые следует отметить:

  • startIndex – это новая переменная. Он представляет собой начальный индекс нашего окна. Рассчитывается как i — maxSize + 1 .
  • Посмотрите на currentSum. Окно стало слишком большим, и наши currentSum теперь неточны! Нам нужно вычесть запаздывающее значение 0.

currentSum теперь больше, чем maxSum . Нам потребуется добавить некоторую логику для обновления maxSum. Я расскажу об этом в коде ниже.

Если бы мы повторили это в четвертой итерации, результат был бы таким же. Теперь, когда мы поняли основную концепцию техники скользящего окна, давайте рассмотрим ее в каком-нибудь коде!

function findMaxSubArraySum(array, maxSize) {
    //error handling
    if(array.length < maxSize) return `error, array is too short`;
    let startIdx = 0;
    let currentSum = 0;
    let maxSum = 0;
    for(let i = 0; i < array.length; i++) {
        currentSum += array[i];
        if(i < maxSize) {
            maxSum = currentSum;
        } else {
            currentSum -= array[i - maxSize];
            if(currentSum > maxSum) {
                maxSum = currentSum;
                startIdx = i - maxSize + 1;
            }
        }
    }
    return array.slice(startIdx, startIdx + maxSize);
}

Как и в случае с доской выше, нам нужно настроить некоторые условия, которые должны быть выполнены для успеха (где мы находим новое maxSumи условие), и условие где мы изменяем размер окна (см. else statementи вложенные if statement).

Наконец, мы используем slice, чтобы вытащить окно, когда закончим. Подводя итог,

  • временная сложность O(n)
  • космическая сложность O(1)

В заключение

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

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