13071 - 最大子段和
时间限制 : 1 秒
内存限制 : 64 MB
给定一个长度为 n 的整数序列 a_1, a_2, \dots, a_n ，请找出一个连续的非空子段，使得该子段内所有整数之和最大。输出这个最大和。
例如，序列 3 1 -6 1 7 5 -2 5 -100 10 的最大子段和为 16（取子段 1 7 5 -2 5）。
输入
- 第一行包含一个整数 n （ 1 \le n \le 10^6 ），表示序列的长度。
- 第二行包含 n 个整数 a_1, a_2, \dots, a_n ,（ |a_i| \le 10^9 ），表示序列中的元素。
输出
输出一个整数，表示最大子段和。
样例
输入
10 3 1 -6 1 7 5 -2 5 -100 10
输出
16
提示
样例说明
最大子段为 1 7 5 -2 5，其和为 1+7+5-2+5 = 16 。
数据范围与约定
- 1 \le n \le 10^6
- |a_i| \le 10^9
来源
动规专题