题目描述
给定序列a [1],a [2],a [3] ...... a [n],你的工作是计算它的最大子序列的和。例如序列6,-1,5,4,-7,该序列中的最大和是6+(- 1)+5+4=14。
输入描述
输入的第一行包含整数T(1 <= T <= 20),表示测试样例的数。然后是T行,每行以数字N(1 <= N <= 100000)开始,然后是N个整数(所有整数都在-1000和1000之间)。
输出描述
对于每组数据,输出两行。第一行是“Case #:”,#表示组号。第二行包含三个整数,分别是序列中的最大子段和,子序列的起始位置,子序列的结束位置。如果有多个结果,则输出第一个结果。两组输出结果间有一个空行。
样例输入
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
样例输出
Case 1:
14 1 4
Case 2:
7 1 6
提示