【问题描述】

给出一串整数a[1],a[2],a[3],…,a[n]，求出它最大的子序列和，即找出1≤i≤j≤n，使a[i]+ a[i+1]+…+a[j]最大。

【输入格式】

第1行1个整数n，表示整数序列的个数。 第2行有n个整数[-32768，32767]，表示a[i]，1≤i≤n。

【输出格式】

输出一行一个数，表示最大的子序列和。

【输入样例】

10
3 1 -6 1 7 5 -2 5 -100 10

【输出样例】

16

【数据规模】

对于30％的数据满足：n≤100。

对于50％的数据满足：n≤10000。

对于80％的数据满足：n≤1000000。

对于l00％的数据满足：n≤10000000。