演習課題「連続するk個の和の最大値」
整数n,kと要素数nの配列aが与えられるので、この数列の連続するk個の整数の和のうち最大のものを出力してください。
入力を受け取るコードがすでに用意されているので、コードを書き足してプログラムを完成させてください。
累積和を使わずに求めてみましょう。
期待する出力値
12
演習課題「連続するk個の和の最大値(累積和)」
整数n,kと長さnの配列aが与えられるので、この数列の連続するk個の整数の和のうち最大のものを出力してください。
入力を受け取るコードがすでに用意されているので、コードを書き足してプログラムを完成させてください。
今度は累積和を使って求めてみましょう。
期待する出力値
12
#03:連続するN個の和の最大値
このチャプターでは、レベルアップ問題集「累積和メニュー」の「連続するN個の和の最大値 4」の問題を解いてみます。
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
# 累積和を格納する長さn+1の配列(リスト)sを0で初期化
s = [0] * (n+1)
# iを0からn-1まで繰り返す
for i in range(n):
# s[i+1]にs[i]+a[i]を代入
s[i+1] = s[i] + a[i]
# 暫定最大値を格納する変数max_sumを0で初期化
max_sum = 0
# iを0からn-kまで繰り返す
for i in range(n-k+1):
# もしs[i+k]-s[i]がmax_sumより大きければ
if s[i+k] - s[i] > max_sum:
# max_sumをs[i+k]-s[i]で更新
max_sum = s[i+k] - s[i]
# max_sumを出力
print(max_sum)
3 2
8 1 3
10 3
1 2 3 4 5 6 7 8 9 10