657. 最大和（Max Sum）

传统题

时间限制：$1000$ms$||$内存限制：$256$MiB 上传者：郑老师($narmo$)

题目描述

给定序列 $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

作者

Ignatius.L https://acm.hdu.edu.cn/showproblem.php?pid=1003 【HDU 题号】1003