[伯俊]2559列を数える

4595 ワード

https://www.acmicpc.net/problem/2559

質問する


毎朝9時に学校で測定した温度がある整数の数列の場合、数日連続の温度の和が最大です.
例えば、10日間の温度が与えられた場合、以下のようになる.
3 -2 -4 -9 0 3 7 13 8 -3
2日間連続したすべての温度の和は以下の通りである.

このとき、温度の和の最大値は21です.
もう1つの例は、上記温度が与えられた場合、5日間連続したすべての温度の和を以下に示す.

このとき、温度の和の最大値は31である.
毎日測定される温度が整数の数列に与えられる場合、数日連続の温度の和の最大値を計算するプログラムを作成します.

入力


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

しゅつりょく


1行目は、入力温度の数列における連続K日の温度の和の最大値を出力する.

に答える


startとend、cur、temp変数が設定されています.
1.tempに温度[end]を加え,endとcurを加えるたびに1増加した.
curがkであればtempが最大値であることを確認し,tempで温度[start]を取り除き,cur 1を取り除く.
3.endがnになるまで1,2を繰り返す.
最大値が0以上でなければならないと考えられるため、50%からエラーが発生します.最大値は0未満の値の中で最大の値である可能性があります.
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
a = list(map(int, input().split()))

start = 0 # 연속적인 k일 시작하는 날
end = 0 # 연속적인 k일 끝나는 날
cur = 0 # 현재 더한 온도의 개수
answer = -(int(1e9)) # 연속적인 k일동안의 온도와 비교해서 최대가 되는 값이면 answer에 저장해준다.
temp = 0

while end < n:
    temp += a[end]
    end += 1
    cur += 1

    if cur == k:
        answer = max(answer, temp)
        temp -= a[start]
        start += 1
        cur -= 1

print(answer)