← 返回题目列表

AtCoder · nikkei2019_final_a

A. 丰富的资源

中文机器翻译题面 查看原题

配点 : 200 点

問題文

有一条东西走向的狭长地带。 这片土地是N 部分从东到西排列,从西 i 第几段是区段 i 。 满足

已知每个地段都有地下资源,并且 i 的资源储量为 A_i 。

1 以上 N 下面的每个整数 查找以下有关 k 问题的答案。 如果选择

  • 连续的 k 路段,那么这些路段的资源储备总和可以考虑的最大值是多少?

制約

  • 1 \leq N \leq 3000
  • 1 \leq A_i \leq 10^9
  • 所有输入值都是整数。 如果您想走

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

N 行。 k 行包含连续的 输出 k 路段总资源储量的最大值。 当


入力例 1

4
4 1 3 3

出力例 1

4
6
8
11

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 ,这是最大值。


入力例 2

5
10 20 30 40 50

出力例 2

50
90
120
140
150

入力例 3

10
61049214 115057849 356385814 932678664 505961980 877482753 476308661 571830644 210047210 873430114

出力例 3

932678664
1438640644
2316123397
2792432058
3364262702
3720648516
4447740026
4804125840
4919183689
4980232903