BOJ 2559번 수열

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

https://upload.acmicpc.net/563b6bfd-12ff-4275-a869-90fdd43b6deb/-/preview/

이때, 온도의 합이 가장 큰 값은 21이다.

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

"""
알고리즘
기법: 투포인터

'연속적인'이란 말이 들어갔음으로 투포인터를 사용할 수 있음

N을 for문으로 돌면서 그 안에서 또 K만큼 반복한다고 하면 O(NK)이다.

N은 2 이상 100,000이하
K는 1과 N 사이의 정수

즉 최악의 경우, 거의 O(n^2)만큼의 수행시간을 가질 수 있다.

그렇다면 다음 연속합을 구할 때, 연속하다는 특성을 활용해서 K만큼 다시 더해주는 것이 아니라, 이전 연속합에 이전 원소를 빼주고 다음 원소를 더해주는 방식으로 다음 연속합들을 구해나간다.

"""

"""
자료구조
1. S: 연속 숫자들을 담을 배열
2. sumValue: 연속합을 기록할 sumValue 변수 하나 
3. maxv: max()를 사용하여 sumValue와 비교하여 최대치를 갱신
    - 초반에 maxv로 최대치를 따로 기록하지 않고, sumValue를 단독으로 사용하면서, sumValue가 반복문을 돌면서도 값이 변하지 않게 되는 실수를 했었음 (max(sumValue, sumValue+S[i]-S[i-k]))
"""

N, K = map(int,input().split())

S = list(map(int,input().split()))

sumValue = 0

for i in range(K):
    sumValue+=S[i]

maxv=sumValue

for i in range(K,N):
    sumValue+=S[i]
    sumValue-=S[i-K]
    maxv = max(maxv, sumValue)

print(maxv)