题目

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

Sample Output

Case 1:
14 1 4

Case 2:
7 1 6

题解

采用递归与分治的思路
类似题目：AOJ 807.算法期末考试C(最大子序列和)

采用与上面题目类似的思路。在找到最大值(更大的值)时，记录子序列的首尾位置。

由于要输出第一个最大的子序列的位置。因此，如果有多组解，应该选取子序列头最小，子序列尾最大的序列。

因此，对于一次递归。
当中间位置左侧不过中间位置最大时，只有中间位置左侧不过中间位置小于经过中间位置才更新；
当经过中间位置不过中间位置最大时，经过中间位置小于中间位置右侧不过中间位置才更新。

需要特别处理只有剩下一个数的情况。

代码

/*
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;
}