問題文
为了运营社交游戏,每天观察用户数量的增减是至关重要的。
经营一家游戏公司的Punch-kun正在尝试找出用户数量增加最多的时期增加了多少用户。
每日用户增加/减少 给定 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 天。