子数列最的和问题

       求解数列中最大和子数列问题
在一个数列中秋节此数列的最大子数列和，并标明字数列的起始位置，如有相等的输出第一个。
开始将这一个问题想得过于简单，不就是不断遍历，同时不断更新最大值的问题吗，于是便用到了两个for循环来解决这个问题。看代码：
#include<stdio.h>
#define maxn 100000+10
int t[maxn];
int main()
{
int n,d=1;
scanf("%d",&n);
while(n>0)
{
  int a=0,max=0,sum=0,b,c;
  scanf("%d",&a);
 
  for(int i=0;i<a;i++)
  {
    scanf("%d",&t[i]);
  }
  for(int i=0;i<a;i++)
  {
     for(int j=i;j<a;j++)
     {
       sum+=t[j];
       if(max<sum)
       { b=i+1;
         c=j+1;
         max=sum;
       } 
     } 
  
     sum=0;
  }
  printf("Case %d:\n",d);
  printf("%d %d %d\n",max,b,c); 
  d++;   
  n--;
  if(n!=0)
  printf("\n");
} 
return 0;
}
很好地解决了这个问题，但是解决问题所耗费的时间确实不尽如人意，数列小的时候还感觉不出来，但一旦数列大了那就蛋疼了。
因此通过看书了解到了一种线性解决这个问题的方法：看代码
  #include<stdio.h>
#define maxn 100000+10
int t[maxn];
int main()
{
int n,d=1;
scanf("%d",&n);
while(n>0)
{ int a,max,sum=0,b=1,c=1,temp=1;
   scanf("%d",&a);
   for(int i=0;i<a;i++)
   {
    scanf("%d",&t[i]);
   }
   max=t[0];
   for(int i=0;i<a;i++)
   {
     sum+=t[i];
    if(sum<t[i])
    {
      temp=i+1;
      sum=t[i];
    }
    if(max<sum)
    {
      max=sum;
      c=i+1;
      b=temp;
    }
   }
  printf("Case %d:\n",d);
  printf("%d %d %d\n",max,b,c); 
  d++;   
  n--;
  if(n!=0)
  printf("\n");
} 
return 0;
}
此方法的原理就是一旦前面的代码有小于零的和出现就将和变为零，当然为了适应具体的问题我进行了一定的改变，线性求解就很好的解决了时间问题，有兴趣可以自己试一下。
将原版的写一下：
#include<stdio.h>
#define maxn 100000+10
int t[maxn];
int main()
{
int n,d=1;
scanf("%d",&n);
while(n>0)
{ int a,max,sum=0,b=1,c=1,temp=1;
   scanf("%d",&a);
   for(int i=0;i<a;i++)
   {
    scanf("%d",&t[i]);
   }
   max=t[0];
   for(int i=0;i<a;i++)
   {
     sum+=t[i];
    if(max<sum)
    {
max=sum;
}else
If(sum<0)
{
sum=0;
}
   }
/*
  printf("Case %d:\n",d);
  printf("%d %d %d\n",max,b,c); 
  d++;   
  n--;
  if(n!=0)
  printf("\n");*/
} 
return 0;
}


[size=large][/size]