Problem D: 最大连续子段和 例题P396【必做】

Problem D: 最大连续子段和 例题P396【必做】

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

SubmitProblemListSolved: 37Submit Num: 92StatisticsShowOff!

Description

给定一个整数序列a，选出其中连续且非空的一段使得这段和最大。

Input

两行。
第一行，一个正整数n。
第二行，n个整数ai。

Output

一个数，最大和。

Sample Input Copy 

7
2 -4 3 -1 2 -4 3

Sample Output Copy 

4

HINT

样例说明：选择3，-1，2这连续的三个数的和最大为4。 
  
数据规模：
对于60%的数据，n<=2*10^3；
对于100%的数据，n<=2*10^5， -10^4<=ai<=10^4。


---
yac
yzs 96498多思路分析
Submit