Алгоритм бегущего окошка

slide_window.ts

// Алгоритм "бегущего окна"
// Сложность - O(k*n), где n - длина массива, k - размер искомой последовательности
// Найти макс сумму из трех последовательных элементов в массиве

const arrInt = [1, 4, 7, 2, 34, 9, 0, 1, 5];

// функция принимает входной массив числел и какое кол-во элементов брать для подмассива
function findMaxSummSubArray(arr: number[], k: number) {
  // сделаем две переменных, одну для хранения суммы, вторая запишем длину входного массива
  let maxSum: number = 0;
  const len: number = arr.length;

  // первый цикл проходит по k элементам и записывает их сумму, это будет наше "окно": 1, 4, 7 = 12
  for (let i = 0; i < k; i++) {
    maxSum += arrInt[i];
  }

  // Делаем переменную где будем хранить следующие суммы подмассивов, записываем туда первую сумму
  let windowSum = maxSum; // 12

  // Запскаем цикл с k до конца массива
  for (let i = k; i < len; i++) {
    // записываем следующую сумму,
    // взяв сумму которую посчитали до этого, вычитаем первый элемент и прибавляем текущий в цикле
    // цикл windowSum = windowSum - arr[3 - 3] + arr[3] => 12 - 1 + 2 (13 > 12)
    // цикл windowSum = windowSum - arr[4 - 3] + arr[4] => 13 - 4 + 34 (43 > 13)
    // цикл windowSum = windowSum - arr[5 - 3] + arr[5] => 43 - 7 + 9  (45 > 43)
    // цикл windowSum = windowSum - arr[6 - 3] + arr[6] => 45 - 2 + 0  (43 < 45)
    //...
    // получается что первая сумма как "окно" движется по массиву и откидвает последний и прибавляет первый
    windowSum = windowSum - arr[i - k] + arr[i];
    // забираем максимальную сумму в сравнении с самой первой
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}