Sliding window

위의 그림과 같이 어떠한 범위가 자동으로 옮겨가면서 조건에 해당하는 답을 변환하는 방식이다.

입출력 예시

maxSubarraySum([100, 200, 300, 400], 2); // 700
maxSubarraySum([1, 4, 2, 10, 23, 3, 1, 0, 20], 4); // 39
maxSubarraySum([-3, 4, 0, -2, 6, -1], 2); // 5
maxSubarraySum([2, 3], 3); // null

배열과 숫자를 매개변수로 받고 숫자에 해당하는 길이의 subarray의 총 합이 가장 큰 배열을 찾는 함수가 있다고 가정 해 보자.

function maxSubarraySum(arr, num) {
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;

  // num 만큼의 숫자의 합계를 구하기 위한 loop이다.
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  
  // Sliding window 개념이다.
  // 범위를 이동 시키면서 원래 있던 범위의 뒤에 있는 값을 더하고 맨 앞에 있는 값을 빼는 방식이다.
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum + arr[i] - arr[i - num];
    maxSum = Math.max(tempSum, maxSum);
  }
  return maxSum;
}

---

maxSubarraySum([100, 200, 300, 400], 2) 일 경우를 살펴보자.

첫번째 loop에서 tempSum은 300, maxSum은 300이 된다.
그리고, 두번째 loop에서는

i = 2 일 때
tempSum 은 300 + 300 - 100 이므로 500이 된다.

i = 3 일 때
tempSum 은 500 + 400 - 200 이므로 700이 된다.

이렇게 loop를 다 돌고 나면 tempSum과 maxSum을 비교하여 더 큰 숫자인 700을 return하게 된다.

위 풀이의 시간복잡도는 O(N)이다.

---