Description

设数组a是有n个元素的整数数组，从中找出最大和子序列。
最大子序和：数组中连续元素（子序列）相加和的最大值。
例如现有数组：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，最大和子序列为16，最大子序列为：5 3 2 -1 6 -9 10

Input Format

共两行， 第一行为一个整数 n， 第二行为 n 个整数。
【数据规模】
对于 20% 的数据， 满足 n<=10
对于 50% 的数据， 满足 n<=100
对于 70% 的数据， 满足 n<=1000
对于 100% 的数据， 满足 n<=1000000  其中n个整数 a_i都在-10000~10000的范围中

Output Format

共1行
一个数， 为数列子串和的最大值。

6
-5 2 6 -7 10 -15

11

Source

动态规划