2559番の数字列

質問する

入力

しゅつりょく

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

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

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)