3005 - 最大子段和
时间限制 : 1 秒
内存限制 : 64 MB
给出一串整数a[1]，a[2]，a[3]，…，a[n]，求出它最大的子段和，即找出1≤i≤j≤n，a[i]到a[j]之间的数相加a[i]+a[i+1]+…+a[j]最大。
输入
第1行1个整数n，表示整数序列的个数。
第2行有n个整数，表示a[i]，1≤i≤n。
输出
输出一行一个数，表示最大的子序列和。
样例
输入
10 3 1 -6 1 7 5 -2 5 -100 10
输出
16
提示
【数据规模】
对于30%的数据满足：n≤10^2。
对于100%的数据满足：n≤10^6。
来源
动规专题