AT_nikkei2019_final_a Abundant Resources

[problemUrl]: https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_a 東西に細長い土地があります。 この土地は、$ N $ 個の区画が東西に並んだ形をしており、西から $ i $ 番目の区画は区画 $ i $ と呼ばれます。 それぞれの区画には地下資源があることがわかっており、区画 $ i $ の資源埋蔵量は $ A_i $ です。 $ 1 $ 以上 $ N $ 以下のそれぞれの整数 $ k $ について、次の問題の答えを求めてください。 - 連続する $ k $ 個の区画を選んだとき、それらの区画の資源埋蔵量の総和として考えられる最大値はいくらか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

$ N $ 行出力せよ。 $ k $ 行目には、連続する $ k $ 個の区画の資源埋蔵量の総和の最大値を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 3000 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - 入力される値はすべて整数である。 ### Sample Explanation 1 $ k=1 $ のとき、区画 $ 1 $ を選ぶと資源埋蔵量の総和は $ 4 $ となり、これが最大です。 $ k=2 $ のとき、区画 $ 3,4 $ を選ぶと資源埋蔵量の総和は $ 3+3=6 $ となり、これが最大です。 $ k=3 $ のとき、区画 $ 1,2,3 $ を選ぶと資源埋蔵量の総和は $ 4+1+3=8 $ となり、これが最大です。 $ k=4 $ のとき、区画 $ 1,2,3,4 $ を選ぶと資源埋蔵量の総和は $ 4+1+3+3=11 $ となり、これが最大です。