C0578 绿洲生态
绿洲生态
题目描述
丝路沿线有 n 个绿洲排成一行，编号 1~n。每个绿洲有一个“生态价值” a[i]（可能为负）。商队要选择一段连续的绿洲进行生态考察，要求该段的价值之和最大。
请输出最大连续子段和。
输入
第一行一个整数 n（1 ≤ n ≤ 10^5）。
第二行 n 个整数 a[1]...a[n]（-10^4 ≤ a[i] ≤ 10^4）。
输出
一个整数，表示最大连续子段和。
数据范围
2≤n≤1000，0≤m≤n*(n-1)/2
输入样例1
9
-2 1 -3 4 -1 2 1 -5 4
输出样例1
6
输入样例2
5
-1 -2 -3 -4 -5
输出样例2
-1
输入样例3
3
1 2 3
输出样例3
6