[Sliding Window] 탐색구간이 정해져 있을 때, 구간합 구하기

/

▷ 슬라이딩 윈도우 알고리즘
탐색 구간이 정해져있을 때 빠른 검색을 위해 사용한다 (시간복잡도를 줄이려고)
만약 탐색 구간이 정해져있지 않다면, Two pointer를 쓰면 된다.

예를 들어) 10개의 정수 중 연속된 3개의 구간의 합이 최대일 경우

그 최대값을 구하라는 문제가 있을 수 있다. 

이미지 출처 : https://velog.io/@zwon/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0Sliding-Window

ex) n개의 정수 중 연속된 m개의 구간의 합이 최대일 경우 그 최대값은?

**
10 5
3 -2 -4 -9 0 3 7 13 8 -3
입력시 출력결과: 31

10 2
3 -2 -4 -9 0 3 7 13 8 -3
입력시 출력결과는: 21

# 슬라이딩 윈도우

n, m = map(int, input().split())
arr = list(map(int, input().split()))
sum = 0

# 첫 M개 구간의 합
for i in range(m):
    sum += arr[i]

Max = sum
# 구간 이동하면서 sum 구하고
# max 값 갱신하기
for i in range(n - m):
    sum += arr[i + m]
    sum -= arr[i]
    if sum > Max:
        Max = sum

print(Max)