1009: 最大子段和

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:95 Solved:47

Description

给定一个长度为$n$的数组$a$,求最大连续子段和(子段长度至少为1)。 ### 输入格式 第一行一个整数$n$,意义如上。$(1 \le n \le 1 \times 10^6)$ 接下来一行$n$个整数,表示数组$a$。$(-10^9 \le a_i \le 10^9)$ ### 输出格式 一个整数,表示结果。 ### 样例输入1 ``` 5 1 2 -4 4 5 ``` ### 样例输出1 ``` 9 ``` 解释:最大子段和为$a_4 + a_5 = 9$。 ### 样例输入2 ``` 6 -1 -2 -3 -5 -2 -3 ``` ### 样例输出2 ``` -1 ```