提示: 欢迎访问OurACM平台。
Problem 1478 环形整数串

Accept: 350    Submit: 1727
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

你知道最大和子串问题么? 就是给你一个整数串,要你求出其中的一个连续子串,要求其和最大。

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

现的问题是如果求环形整数串的最大连续和子串呢?

请编写一个程序解决这个问题。

Input

本题有多组输入数据,你必须处理到EOF为止

每组数据的第一行有一个整数n, (1<=n<=1000000).第2行有n个整数,每个整数都在[-100,100]的范围内

Output

每组数据输出一个整数,表示环形整数串最大连续子串和。

Sample Input

6 -2 3 0 1 -48 80 2 1 3

Sample Output

82 4

Source

FOJ月赛-2007年3月

Submit  Back  Status  Discuss