问题 4217 --1.数列游戏 (sequence)

4217: 1.数列游戏 (sequence)

题目描述

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

输入

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

输出

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

样例输入输出

输入#1 复制
10
-562 232 969 201 -111 378 -610 127 245 932
输出#1 复制
2363
输入#2 复制
10
868 -838 -958 200 867 -920 -493 114 -800 757
输出#2 复制
2828
输入#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

序号 标题 作者 发表时间 费用 订购数 操作