Maximum Sum Sequence

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

和の最大値

与えられた整数の並び a1, a2, a3,... , an について、連続した項(1つ以上)の和の最大値を出力するプログラムを作成して下さい。

Input

複数のデータセットが与えられます。各データセットは以下のような形式です。

n
a1
a2
:
an

1行目に項数を表す整数 n (1 ≤ n ≤ 5000) が与えられます。続く n 行に第 i 項を表す整数 ai (-100000 ≤ ai ≤ 100000) が与えられます。

n が 0 のとき入力の最後とします(この場合は処理をしない)。

Output

各データセットに対して、連続した項の和の最大値を1行に出力して下さい。

Sample Input

7
-5
-1
6
4
9
-6
-7
13
1
2
3
2
-2
-1
1
2
3
2
1
-2
1
3
1000
-200
201
0

Output for the Sample Input

19
14
1001

Source: PC Koshien 2003 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2003
(extended)
http://www.pref.fukushima.jp/pc-concours/