C - ソーシャルゲーム
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ソーシャルゲームを運営するためには、日々のユーザ数の増減を観察することが欠かせません。
ゲーム会社を運営しているパンチくんは、最もユーザが増加した期間に、何人ユーザが増加したかを調べようとしています。
日々のユーザの増減数 a_1, a_2, …, a_N が与えられるので、ユーザ数の増減数が最大となる期間のユーザの増減数を求めて下さい。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_N
- 1 行目には、調査対象となる期間の日数 N (1 ≦ N ≦ 100000) が与えられる。
- 2 行目には、調査対象となる期間の i 日目のユーザの増減数 a_i (-1000 ≦ a_i ≦ 1000) が与えられる。
部分点
1 ≦ N ≦ 3000 を満たすテストケースに正解した場合、部分点として 40 点が与えられる。
出力
ユーザの増減数が最大となる期間( 1 日以上)のユーザ増減数を、 1 行で出力せよ。出力の末尾には改行をいれること。
入力例1
7 3 -4 2 3 -1 2 -1
出力例1
6
3 日目から 6 日目までの、 (2, 3, -1, 2) の増加数 6 が最大です。
入力例2
3 10 20 30
出力例2
60
全期間が、ユーザの増減数が最大となる期間となります。
入力例3
3 -4 -2 -5
出力例3
-2
出力はマイナスとなることがあります。 出力対象となる期間は 1 日以上であることに注意して下さい。