C0583 绿洲生态
绿洲生态
题目描述
丝路沿线有 n 个绿洲排成一行，编号 1~n。每个绿洲有一个“生态价值” a[i]（可能为负）。商队要选择一段连续的绿洲进行生态考察，要求该段的价值之和最大。
请输出最大连续子段和。
输入
第一行一个整数 n 。
第二行 n 个整数 a[1]...a[n] 。
输出
一个整数，表示最大连续子段和。
数据范围
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