2066 - 【入门】最大子段和进阶

给你一个序列,请你计算这个序列的最大子段和。

注意这个序列收尾是相连的。

例如:

1 -2 -3 4

的最大子段和是 5

输入

输入一个整数 n 表示有 n 个整数。

接下来一行有 n 个整数 a[i]

输出

输出一个整数表示这个序列的最大子段和。

数据范围 n \le 10^3, -10^9 \le a[i] \le 10^9

样例

输入

4
-1 2 -1 4

输出

5

输入

4
1 -2 -3 4

输出

5

提示

枚举两个端点,遍历所选出的子段求和。然后找到其中的最大值。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题