5370: 最大子段和 I
[Creator : ]
Description
有一个整数数列，求该数列的最大子段和。子段是指数列中一段连续的数字，可以是 $1$ 个数，也可以是若干个数。
例如数列 {$-1,\ 3,\ -2,\ 5,\ 3,\ 2,\ -3,\ -6$}，其中的 {$-1,\ 3,\ -2$}、{$3$}、{$3,\ -2$} 都是一个子段。
给出一个数列，求出可以得到的最大的子段和。
例如数列 {$-1,\ 3,\ -2,\ 5,\ 3,\ 2,\ -3,\ -6$}，其中的 {$-1,\ 3,\ -2$}、{$3$}、{$3,\ -2$} 都是一个子段。
给出一个数列，求出可以得到的最大的子段和。
Input
输入包含两行：
第一行：一个正整数 $n$，表示接下来要输入 $n$ 个整数（$1 \leq n \leq 2\times 10^5$）。
第二行：$n$ 个整数，每个整数之间用空格隔开，数值在 $[-10^9, 10^9]$ 之间。
第一行：一个正整数 $n$，表示接下来要输入 $n$ 个整数（$1 \leq n \leq 2\times 10^5$）。
第二行：$n$ 个整数，每个整数之间用空格隔开，数值在 $[-10^9, 10^9]$ 之间。
Output
输出一行，数列的最大子段和。
Sample 1 Input
8
-1 3 -2 5 3 2 -3 -6
Sample 1 Output
11
最大的子段是：$\{3\ -2\ 5\ 3\ 2\}$
它的和为：$3+(-2)+5+3+2=11$
它的和为：$3+(-2)+5+3+2=11$
Sample 2 Input
7
2 -4 3 -1 2 -4 3
Sample 2 Output
4
子段 $\{3,\ -1,\ 2\}$，其和为 $4$。
Sample 3 Input
6
-2 -1 -3 -5 -2 -3
Sample 3 Output
-1
HINT
相同题目：洛谷 P1115。