1646 - 第四届“恒生杯”程序设计大赛决赛 D

Time Limit: 1s Memory Limit: 256MB

Submissions: 163 Solved: 32
Description

skyjiange get a array A consist of n integers, he want to know what is the maximum absolute sum in all sub-arrays, sub-arrays is some array A[i...j], absolute sum is equal to |sum(A[i...j])|.

Input

each line contains a integer n(1<=n<=100000), follow by n integers(|A[i]|<=10000).

Output

print the maximum abs sum.

Sample Input
3 1 -2 5 
3 2 -1 5
Sample Output
5
6
Hint
Source