Preparing NOJ

罗马PK

1000ms 65536K

Description:

一天,机智的罗老师和小马哥想比试以下到底谁更机智,于是他们找到了一个很长的数列串,决定看谁能更快地算出这条长串中子串和的最大值。

这对于身经百战的神牛们通过编程来求解真是小菜一碟,现在想请你帮他们算出正确结果。

eg.长串为(6,-1,5,4,-7),那么子串的最大值为:

6+(-1)+5+4=14


Input:

输入的第一行包含一个整数T(1<=T<=20)表示测试用例的数目。接下来有T行输入,每行以一个数N(1<=N<=100000)开头,然后接下来输入N个整数(所有的整数都在-10001000之间)。

Output:

对于每个测试用例,你应该输出2行。第一行是 "Case #:"#表示测试用例数。第二行包含3个整数,子串和的最大值,对应字串的开始位置,对应字串的结束位置。如果有超过一个的答案,输出第一个。每两个测试用例之间有一个空白行。

Sample Input:

2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Sample Output:

Case 1:
14 1 4

Case 2:
7 1 6

Note:

undefined

本题由旧版NOJ导入,来源:B12040705

Info

NOJ

Provider NOJ

Code NOJ2045

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet