# 2559번 수열

'''
10개의 원소가 있고 3 크기의 윈도우를 슬라이딩 시킨다고 하면
0 1 2 3 4 5 6 7 8 9
|___| | | | | | | |
  |___| | | | | | |
    |___| | | | | |
      |___| | | | |
        |___| | | |
          |___| | |
            |___| |
              |___|
반복 횟수는 10 - 3 + 1 = 8회다.

최초 윈도우를 설정하는1회를 제외한 7회동안 
제일 앞과 제일 뒤의 값을 빼고 더하면 된다.
n개의 원소와 k크기의 윈도우라면 n-k회가 된다.
'''

import sys
def sliding_window_sum(arr, n, k):
    window = sum(arr[0:k])
    result = window
    for i in range(n-k):
        window = window - arr[i] + arr[i+k]
        result = max(result, window)       
    return result

if __name__ == "__main__":
    n, k = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))
    print(sliding_window_sum(arr, n, k))

이 문제에 다음 세 알고리즘이 관련으로 나와서 공부해 보았다.

누적합은 점점 구간이 길어지고 투 포인터는 조건에 따라 길어졌다가 짧아졌다 하며, 슬라이딩 윈도우는 구간 길이를 유지한다.

누적 합(Prefix Sum) 문제

배열에서 시작점부터 점점 긴 구간을 합하는 문제인데, 새로운 구간만 더해서 복잡도를 낮추는 개념입니다.

https://book.acmicpc.net/algorithm/prefix-sum

누적 합

투 포인터(Two Pointer)

https://butter-shower.tistory.com/226

[Algorithm] 투포인터(Two Pointer) 알고리즘

슬라이딩 윈도우(Sliding Window)

https://ji-musclecode.tistory.com/37

슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트)

https://celbeing.tistory.com/75

슬라이딩 윈도우(Sliding window)