C - ソーシャルゲーム 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MiB

問題文

ソーシャルゲームを運営するためには、日々のユーザ数の増減を観察することが欠かせません。

ゲーム会社を運営しているパンチくんは、最もユーザが増加した期間に、何人ユーザが増加したかを調べようとしています。

日々のユーザの増減数 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 日以上であることに注意して下さい。