2559番の数字列

質問する

毎朝9時に学校で測定した温度がある整数の数列の場合、数日連続の温度の和が最大です.
例えば、10日間の温度が与えられた場合、以下のようになる.
3 -2 -4 -9 0 3 7 13 8 -3
2日間連続したすべての温度の和は以下の通りである.
https://upload.acmicpc.net/563b6bfd-12ff-4275-a869-90fdd43b6deb/-/preview/
このとき、温度の和の最大値は21です.
もう1つの例は、上記温度が与えられた場合、5日間連続したすべての温度の和を以下に示す.
このとき、温度の和の最大値は31である.
毎日測定される温度が整数の数列に与えられる場合、数日連続の温度の和の最大値を計算するプログラムを作成します.

入力

最初の行には2つの整数NとKがあり、1つのスペースを隔てて、順番に与えられます.最初の整数Nは、温度を測定する全日付の数である.Nは2以上100000以下である.2番目の整数Kは、和を求める連続日数である.Kは1とNの間の整数である.2行目にはN個の整数があり、毎日測定される温度を表す.これらの数字はすべて-100以上100以下です.

しゅつりょく

1行目は、入力温度の数列における連続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)