連続する N 個の和の最大値 1 PHP編（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 個の整数の和の最大値を求めることができます。

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