PID208 / 奥运火炬到厦门
题目描述

背景:5月12日,在厦门人民的热烈欢迎下,象征着和平、友谊、圣洁的奥运火炬终于来到了厦门,开始了传递……

描述:厦门市市长宣布:“要把这次火炬接力办的很有意义。”“有意义”是什么意思呢?厦门市市长别出心裁地给它下了个定义:每个火炬手都有个意义值,可以将他们顺次看作一个首尾相接的环,而整个火炬接力的意义值是这个环的最大和连续子串。

比如: 串是 -2 2 0 1 -48 1,显然其最大和连续子串是2 0 1,其和是3。

现在给定n个火炬手的意义值,请算出整个火炬接力的意义值(意义值可能为负数)

输入格式

第1行一个整数n(1<=n<=1000000)表示n个火炬手

第2行有n个整数,每个整数都在longint的范围内。

新备注:因为未知原因,导致正常程序在测评8 9 10三个测试点时TLE,所以本题暂时关闭后3个测试点。数据范围改为5000

输出格式

火炬接力的意义值。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论