Problem1706--最大连续和

1706: 最大连续和

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

给出一个长度为n的序列A1,A2,...,An,求最大连续和。换句话说,要求找到1≤i≤j≤n,使得Ai+Ai+1+...+Aj尽量大。

Input

第一行是一个整数,表示序列的长度 n。n≤106

第二行有n个整数,第i个整数表示序列的第i个数字10-5Ai≤105 



Output

输出一个整数表示最大连续和。

Sample Input Copy

7
2 -4 3 -1 2 -4 3

Sample Output Copy

4

Source/Category