Problem 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

Solution

最初看到这题时的想法就是做循环,心里很明白这样做会超时,但还是去试了下,果然超时了,之后就暂时放下了这个问题。后来在《编程珠玑》里看到了对这个问题的详细讲解,豁然开朗,于是又重新做了一遍,感觉顺手多了。

《编程珠玑》看里给出了几种算法的比较,第一种自然是最简单的时间复杂度为O(n^3)的算法,然后可以改进为O(n^2)的算法,之后作者提到可以用分治法的思想,通过递归解决,时间复杂度为O(n*logn),而且这种方法在很长一段时间里被认为是最优的,直到某天遇到了一数学大神,据说该大神几分钟就想出了一个时间复杂度为O(n)的算法、、、

杭电的这题更复杂一点的地方在于它还要求出最大子序列的开始和结束位置,结束位置很简单,直接是Max的最后一个数,第一个当初想是从最后一个数向前做加法,直到和为Max,但是这样还要在判断这之前的数是否为0,很复杂,后来发现讨论区里有代码,研究了下,很巧妙,下面程序附的测试用例也是讨论区看到的、、、

Code

#include <stdio.h>
#define MAX_LEN 100000

int main( int argc, char *argv[] ) {
    int T,count = 0;
    scanf("%d",&T);

    while(T--) {
        ++count;
        int i,length;
        int a[MAX_LEN+1];
        scanf("%d",&length);

        for( i=0; i < length; i++ ) {
            scanf("%d",&a[i]);
        }

        int left = 0,right = 0,tmpLeft = 0;
        int max = a[0],maxWithLastNumber = 0;   //需要注意数列全为负,故不能将max初始化为0
        for( i = 0; i < length; i++ ) {
            maxWithLastNumber += a[i];          //数列全为负且第一个可能不是最大的负数,所以不能先比较maxWithLastNumber
            if( max < maxWithLastNumber ) {
                max = maxWithLastNumber;
                left = tmpLeft;
                right = i;
            }
            if( maxWithLastNumber < 0 ) {
                maxWithLastNumber = 0;
                tmpLeft = i+1;
            }
        }
        printf("Case %d:\n%d %d %d\n",count,max,left+1,right+1);
        if( T ) {  printf("\n");  }
    }
    return 0;
}
//附测试数据
/*
    4 0 0 2 0 -> 2 1 3
    6 2 7 -9 5 4 3 -> 12 1 6
    4 0 0 -1 0 -> 0 1 1
    7 -1 -2 -3 -2 -5 -1 -2 -> -1 1 1
    6 -1 -2 -3 1 2 3 -> 6 4 6
    5 -3 -2 -1 -2 -3 -> -1 3 3
*/