99클럽 코테 스터디 5일차 TIL - 수열 (슬라이딩 윈도우)

https://www.acmicpc.net/problem/2559

접근방식

슬라이딩 윈도우를 활용해서 효율적으로 구현할 수 있다.
처음에 K개의 합을 구한 다음, 앞 요소를 하나 빼고 새 요소를 하나 더하는 방식으로 K개의 합을 갱신한다.
전체를 매번 더하면 O(N*K)이지만, 슬라이딩 윈도우를 활용하면 O(N)으로 줄일 수 있다.

구현

const fs = require("fs")
const [[n, k], arr] = fs.readFileSync("/dev/stdin").toString().split("\n").map(s => s.split(" ").map(Number))

let maxSum = temp = arr.slice(0, k).reduce((a, b) => a + b, 0)
for (let i = k; i < n; i++) {
  temp += arr[i] - arr[i - k]
  maxSum = Math.max(temp, maxSum)
}

console.log(maxSum)