4971 - 最大子区间
题目描述
给定一个数组，从数组中取出若干个连续的元素（至少取一个元素）称为数组的子区间。
请求出数组中所有子区间的和的最大值。
输入
第一行一个整数 n。（1 ≤ n ≤ 100）
第二行 n 个整数 a[i]。（-1000 ≤ a[i] ≤ 1000）
输出
输出一个整数，表示子区间和的最大值。
样例
输入
4 10 -20 40 30
输出
70
输入
5 -2 -5 -5 -6 -9
输出
-2
说明
样例 1 解释：
样例 1 共有 4 个元素，能取出的子区间共有 10 个，他们的下标范围分别是：[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [3, 4], [4, 4]。
其中，子区间的最大和为下标范围在 [3, 4] 区间内的两个元素，子区间的和为 40+30=70。
标签
