本文共 3887 字，大约阅读时间需要 12 分钟。

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

有2种方法做，我开始不明白题目意思，走了很多弯路。

题目要求是这样的： 输出数组的子序列的最大值。 如果有相同的，开始序列输出小的。 结尾序列输出大的。

/**1003题**/#include 
   
    #include 
    
     int a[1000020];long long int c[3000020],b[1000020];int main(){    int t,tt=1;    scanf("%d",&t);    while(t--)    {        int i,j,n,a1,a2;        scanf("%d",&n);        int age=0;        if(n!=1)        {            for(i=0; i
     
      =0)                {                    a1=a2=i+1;                    age=1;                    break;                }            }            if(age!=1)            {                int max=a[0];                a1=a2=1;                for(i=1; i
      
       max)                    {                        max=a[i];                        a1=a2=i+1;                    }                }                printf("Case %d:\n",tt);                tt++;                printf("%d %d %d\n",max,a1,a2);                if(t!=0)                    printf("\n");            }            else            {                int k=0;                c[k]=0;                long long int max=c[k];                for(i=a1-1;i
       
        i+1)                                a1=i+1;                            if(a2
       
      
     
    
   

第二种方法：

#include
   
    int main(){    int i,ca=1,t,s,e,n,x,now,before,max;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(i=1; i<=n; i++)        {            scanf("%d",&now);            if(i==1)//初始化            {                max=before=now;//max保留之前算出来的最大和，before存储目前在读入数据前保留的和，now保留读入数据                x=s=e=1;//x用来暂时存储before保留的和的起始位置，//当before>max时将赋在s位置，s，e保留最大和的start和end位置            }            else            {                if(now>now+before)  //如果之前存储的和加上现在的数据比现在的数据小，//就把存储的和换成现在的数据，反之就说明数据在递增，可以直接加上                {                    before=now;//预存的位置要重置                }                else before+=now;            }            if(before>max)//跟之前算出来的最大和进行比较，如果大于，位置和数据就要重置                max=before,s=x,e=i;        }        printf("Case %d:\n%d %d %d\n",ca++,max,s,e);        if(t)printf("\n");    }    return 0;}
   

#include 
   
      using namespace std;  int T,n,m;  int post1,post2,x;//post1表示序列起点，post2表示序列终点，x表示每次更新的起点  int max,now;//max表示最大子序列和，now表示各个子序列的和  int i,j;  int main ()  {      scanf ("%d",&T);      for (i=1; i<=T; i++)      {          scanf ("%d%d",&n,&m);          max = now = m;          post1 = post2 = x = 1;//初始化          for (j=2; j<=n; j++)          {              scanf ("%d",&m);              if (now + m < m)//对于每个数，如果该数加上当前序列和比本身还小              {                  now = m;//更新区间                  x = j;//更新起点              }              else              now += m;//否则把该数加进序列              if (now > max)//如果当前序列和比已有最大序列和大，更新              {                  max = now;                  post1 = x;//记录新的起点和终点                  post2 = j;              }          }          printf ("Case %d:\n",i);          printf ("%d %d %d\n",max, post1, post2);          if (i != T)          printf ("\n");      }      return 0;  }
   

转载地址：https://chenhx.blog.csdn.net/article/details/48598777 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！