子数列最的和问题
求解数列中最大和子数列问题
在一个数列中秋节此数列的最大子数列和，并标明字数列的起始位置，如有相等的输出第一个。
开始将这一个问题想得过于简单，不就是不断遍历，同时不断更新最大值的问题吗，于是便用到了两个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]
