Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 1 Contest LoginRegister Exam
Problem 2002. -- 算法实验3:最大子段和

算法实验3:最大子段和

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 3074  Solved: 1336
[Submit][Status][Discuss]

Description

给定有n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列连续的子段和的最大值。 如果该序列的所有元素都是负整数时定义其最大子段和为0。

Input

第一行有一个正整数n(n<1000),后面跟n个整数,绝对值都小于10000。直到文件结束。

Output

输出它的最大子段和。

Sample Input

6 -2 11 -4 13 -5 -2

Sample Output

20

HINT

分别用普通O(n 3 )或O(n 2 )、分治O(nlogn)和动态规划O(n)实现。做出后可以再做 To the Max

Source

[Submit][Status][Discuss]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin