설명

[1, 2, 3, 4, 5, 6, 7] 배열에서 세가지 수의 합이 가장 큰 수를 구하라

해당 알고리즘의 원리가 윈도우를 옆으로 쭉쭉 밀어나가면서 답을 구하는 느낌(?)이라서 슬라이딩 윈도우인 것 같다.

이 때, 주목할 점은 윈도우(선택된 배열)이 한칸씩 이동할 때마다, 윈도우의 맨 앞의 요소는 빼주고, 윈도우의 맨 뒤의 요소는 더해준다는 것이다.

[1,2,3] => [2,3,4]로 이동할 때, 윈도우에서 1은 빼주고 4를 더해 준다

이를 코드로 나타내면 다음과 같다. (i는 index값)

curSum = curSum - arr[i - 1] + arr[i + 3 - 1];

1. 먼저 처음 윈도우 [1,2,3] 의 합을 구하면 == 6

2. 다음 윈도우인 [2,3,4]는 [1,2,3] 윈도우에서 처음 값이 빠지고, 그 다음 값인 4가 들어온다. 따라서 합은 (6-1+4) == 9 입니다.

3. 다음 윈도우의 합은 이전 윈도우에서 처음 값을 빼고 다음에 들어올 값을 더해주면 된다.

[1, 2, 3], 4, 5, 6, 7

1, [2, 3, 4], 5, 6, 7

1, 2, [3, 4, 5], 6, 7

1, 2, 3, [4, 5, 6], 7

1, 2, 3, 4, [5, 6, 7]

예제

문제

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속 된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면
12 15 11 20 25 10 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요.

입력설명

첫 줄에 N(5<=N<=100,000)과 M(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

출력설명

첫 줄에 최대 매출액을 출력합니다.

입력예제

10 3
12 15 11 20 25 10 20 19 13 15

출력예제

56

슬라이딩 윈도우로 해결한 코드

const one = (n, windowSize, arr) => {
  let curSum = 0; // 현재 윈도우의 합
  let maxSum = 0; // 최대매출액 === 윈도우의 합의 최대값 
  for (let i = 0; i < n- windowSize + 1; i++) {
    if (i===0) {
      let sum = 0;
      for (let i=0; i<windowSize; i++) {
        sum += arr[i];
      }
      curSum = sum;
    } else {
      curSum = curSum - arr[i-1] + arr[i+ windowSize-1];
    }
    if(curSum > maxSum) maxSum = curSum;
  }
  return maxSum;
};

//console.log(one(10, 3,[12, 15, 11, 20, 25, 10, 20, 19, 13, 15]));