2065 - 【入门】最大子段和
Time Limit : 1 秒
Memory Limit : 128 MB
给定一个由数字组成的序列，其中连续的一段子序列称为一个子段，子段中的所有数之和称为子段和，这里只考虑非空子段，即至少包含一个元素的子段。
最大子段和 即一个序列中子段和最大的子段的子段和。
Input
输入一个整数 n 表示有 n 个整数。
接下来一行有 n 个整数 a[i]。
Output
输出一个整数表示这个序列的最大子段和。
数据范围 n \le 10^3, -10^9 \le a[i] \le 10^9
Examples
Input
4 -1 2 -1 4
Output
5
Hint
枚举两个端点，遍历所选出的子段求和。然后找到其中的最大值。