# 题目

## Description

Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

## Input

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

## Output

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

## Sample Input

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

# 代码

```/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！

*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int maxn = 100005;
//const int INF = (1 << 31) - 1;
const int INF = 0x7fffffff;

int a[maxn];

int dfs(int *a,int l,int r,int &begin,int &end) {
if(l == r) {
begin = end = l;
return a[l];
}
if(l > r) {

begin = end = -1;
return -INF;
}

int mid = (l + r) / 2;
int Max;
int ans;
int tbegin,tend;
begin = end = mid;

//中间
int i;

ans = 0;
int maxl = 0;
for(i = mid - 1;i >= l;i--) {
ans += a[i];
if(ans >= maxl) {
maxl = ans;
begin = i;
}
}

ans = 0;
int maxr = 0;
for(i = mid + 1;i <= r;i++) {
ans += a[i];
if(ans > maxr) {
maxr = ans;
end = i;
}

}

Max = maxl + a[mid] + maxr;

//左侧
ans = dfs(a,l,mid - 1,tbegin,tend);
if(ans >= Max) {
Max = ans;
begin = tbegin;
end = tend;
}

//右侧
ans = dfs(a,mid + 1,r,tbegin,tend);
if(ans > Max) {
Max = ans;
begin = tbegin;
end = tend;
}

return Max;
}

void Do() {
int n,l,r;
scanf("%d",&n);

for(int i = 1;i <= n;i++)
scanf("%d",&a[i]);

int ans = dfs(a,1,n,l,r);
printf("%d %d %d\n",ans,l,r);
return;
}

int main() {

int T;
scanf("%d",&T);
for(int i = 1;i <= T;i++) {
if(i != 1)
printf("\n");
printf("Case %d:\n",i);
Do();
}
return 0;
}
```