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

题意为求这段数据里面的最小子段和，并将其始末位置输出！

本来是一个初识入门的dp题目，可是这之间的思路应该好好理理！！

怎样能想到这个方法？

首先一长串数字的字段我们如果去暴力肯定是会超时的！那么这其中是否有一些潜在的规律？

我们来思考一下！最大子段和，该段的总和是最大的，那么！该段前面的一段总和肯定是负数！！否则该子段不是还可以增大？然后，我们既然不能一个个来计算子段，那么我们整体考虑，所有的子段都加上前面那一段负数大小关系是不会改变的吧！那么我们就用一个数组记录从第一个数字开始的子段和，找到最大值那么最大子段一定在这一段数字里面，怎么找出来呢？

于是就是刚才说的前面一段是负数，找到了一减去就ok！这个思路得理清！

#include 
    
     #include
     
      #include 
      
       using namespace std;int a[100005],f[100005];int main(){    int t;    cin>>t;    for(int i=0;i
       
        >n;        for(int j=0;j
        
         >a[j];f[j]=a[j];}        for(int j=1;j
         
          =0) f[j]=a[j]+f[j-1]; int max0=-1001,k,x=0; for(int j=0;j
          
           max0) {max0=f[j];k=j;} for(int j=k-1;j>=0;j--) if(f[j]<0) { x=j+1;break; } cout<<"Case "<
           
            <<':'<