You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小明最近为了锻炼智力，在玩一个数列求和的游戏。设数列的长度为n，每一个数字都是整数，且在[-1000,1000]范围内，即范围是-1000~1000。 游戏规则：小明可以从这个数列里面选一串任意长度的连续子串并求和，小明想知道子串和绝对值的最大值是多少，你能帮帮他吗？ 绝对值：正数的绝对值为本身，负数的绝对值为它的相反数。如5的绝对值为5，-7的绝对值为7。

输入格式

输入共两行，第一行为一个整数n，第二行为n个整数。

输出格式

输出一个数，为数列子串和绝对值的最大值。

样例 #1

样例输入 #1

10 
-562 232 969 201 -111 378 -610 127 245 932

样例输出 #1

2363

样例 #2

样例输入 #2

10 
868 -838 -958 200 867 -920 -493 114 -800 757

样例输出 #2

2828

样例 #3

样例输入 #3

10 
-607 -260 -270 -833 560 -280 404 -542 560 -115

样例输出 #3

1970

样例解释

对于样例1，可以发现232 + 969 + 201 - 111 + 378 - 610 + 127 + 245 + 932 = 2363，所以2363是最大的绝对值。 对于样例2，可以发现-838 + -958 + 200 + 867 + -920 + -493 + 114 + -800 = -2828，所以2828是最大的绝对值。

数据范围

• 对于20%的数据，满足 (n<=10)
• 对于50%的数据，满足 (n<=100)
• 对于70%的数据，满足 (n<=1000)
• 对于100%的数据，满足 (n<=1000000)