1. paizaラーニングトップ
  2. レベルアップ問題集
  3. 累積和メニュー(言語選択)
  4. 問題一覧
  5. 連続する N 個の和の最大値 1

累積和メニューのサムネイル
連続する N 個の和の最大値 1 (paizaランク C 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

10 個の整数 a_0, a_1, a_2, ..., a_9 をそれぞれ

1 5 9 7 5 3 2 5 8 4

としたとき、連続する 3 個の整数の和の最大値を、累積和を使うことで求め、一行で出力してください。





(ヒント)


まず、数列 a_0, a_1, ..., a_(N-1) に対して、数列 s_0, s_1, ... s_N を以下のように考えます。



s_0 = 0
s_1 = a_0
s_2 = a_0 + a_1
s_3 = a_0 + a_1 + a_2
...
s_N = a_0 + a_1 + ... + a_(N-1)


次に、連続する 3 個の整数の和とはどのようなものかを考えると、


・a_0 + a_1 + a_2
・a_1 + a_2 + a_3
・a_2 + a_3 + a_4
...
・a_7 + a_8 + a_9

となります。



つまりこの問題は、これらの数の最大値を求める問題であると考えることができます。

また、これを数列 s で表すと、それぞれ以下のようになります。


・s[3] - s[0]
・s[4] - s[1]
・s[5] - s[2]
...
・s[10] - s[7]

これを一般化すると、
s[i+3] - s[i] (0 ≦ i ≦ 7)

と考えることができます。

あとはこれをループなどを用いて実装することで、連続する 3 個の整数の和の最大値を求めることができます。



このヒントを元に、累積和で問題を解いてみましょう

入力される値

・入力はありません。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

連続する 3 個の整数の和の最大値を、累積和を使うことで求め、一行で出力してください。

末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件

・入力はありません。

問題一覧へ戻る

ページの先頭へ戻る