#657. 最大和（Max Sum）

ID: 657 | 传统题 | 时间限制：1000ms | 内存限制：256MiB | 尝试：1 | 已通过：1 | 难度：10 | 上传者：郑老师(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