最大连续和问题
给出一个长度n的序列：A1，A2，A3，……，An。求最大连续子段和。
即：要求找到1<=i<=j<=n，使得A[i]+ A[i+1]+……+A[j]尽量大。
题目来源：
洛谷OJ： P1115 最大子段和
题目描述
给出一段序列，选出其中连续且非空的一段使得这段和最大。
输入格式：
输入文件maxsum1.in的第一行是一个正整数N，表示了序列的长度。
第2行包含N个绝对值不大于10000的整数A[i]，描述了这段序列。
输出格式：
输入文件maxsum1.out仅包括1个整数，为最大的子段和是多少。子段的最小长度为1。
输入样例#1：
7
2 -4 3 -1 2 -4 3
输出样例#1：
4
【数据规模与约定】
对于40%的数据，有N ≤ 2000。
对于100%的数据，有N ≤ 200000。
下面的代码实现了四种计算最大子段和的算法。
1 #include<stdio.h> 2 #include<stdlib.h> 3 long long fun1(int a[],int n)//返回最大连续子段和。O(n^3)，可以获取子段位置 4 { 5 int i,j,k; 6 long long best=a[0],sum;//初始最大值 7 int bestI=0,bestJ=0; 8 9 for(i=0;i<n;i++) 10 { 11 for(j=i;j<n;j++) 12 { 13 sum=0; 14 for(k=i;k<=j;k++) sum=sum+a[k]; 15 if(sum>best) { best=sum; /*bestI=i; bestJ=j;*/ } 16 } 17 } 18 return best; 19 } 20 long long fun2(int a[],int n)//返回最大连续子段和。O(n^2)，可以求得子段的位置。 21 { 22 int *s=(int *)malloc(sizeof(int)*n); 23 int i,j,bestI=0,bestJ=0; 24 long long best,sum; 25 26 s[0]=a[0]; 27 for(i=1;i<n;i++) s[i]=s[i-1]+a[i]; 28 29 best=a[0]; 30 for(i=0;i<n;i++) 31 { 32 for(j=i;j<n;j++) 33 { 34 if(i==0) sum=s[j]; 35 else sum=s[j]-s[i-1]; 36 best=(sum>best?sum:best); 37 //if(sum>best) { best=sum; bestI=i; bestJ=j; } 38 } 39 } 40 free(s); 41 return best; 42 } 43 long maxSum(int a[],int x,int y)//返回序列a[]在下标[x,y)范围内的最大子段和。O(nlogn)，无法求得最大子段位置 44 { 45 long mid,V,L,R; 46 long max,s1,s2,s3; 47 int i; 48 49 if(y-x==1)return a[x];//假如只有一个元素，最大子段和就是该元素本身 50 51 mid=x+(y-x)/2;//分治法第一步：划分为[x，m)和[m，y)两个子段 52 s1=maxSum(a,x,mid);//分治法第二部：递归求解 53 s2=maxSum(a,mid,y); 54 max=(s1>s2?s1:s2); 55 56 V=0;L=a[mid-1];//分治法第三步：合并（1）——从分界点开始往左的最大连续子段和 57 for(i=mid-1;i>=x;i--) { V=V+a[i]; L=(V>L?V:L); } 58 59 V=0;R=a[mid];//分治法第三步：合并（2）——从分界点开始往右的最大连续子段和 60 for(i=mid;i<y;i++) { V=V+a[i]; R=(V>R?V:R); } 61 62 V=L+R; 63 return (V>max?V:max);//把子问题的解与L+R比较 64 } 65 long fun4(int a[],int n)//返回a[]的最大子段和 66 { 67 long temp,sum; 68 int i; 69 temp=a[0];sum=a[0]; 70 for(i=1;i<n;i++) 71 { 72 if(temp<0) temp=a[i]; 73 else temp=temp+a[i]; 74 if(temp>sum) sum=temp; 75 } 76 return sum; 77 } 78 int main(int argc, char *argv[]) 79 { 80 int n,i,a[200003]; 81 long long ans; 82 //freopen("testdata.in","r",stdin); 83 84 scanf("%d",&n); 85 for(i=0;i<n;i++) scanf("%d",&a[i]); 86 //ans=fun1(a,n); //超时 87 //ans=fun2(a,n); //得部分分，其余测试点超时 88 //ans=maxSum(a,0,n); //AC 89 ans=fun4(a,n); //AC 90 printf("%lld\n",ans); 91 return 0; 92 }
动规算法经过修改也可以得到最大连续子段和的位置。参考51Nod动态规划基础篇的内容
1 long long fun5(int a[],int n)//返回a[]的最大子段和，子函数内部输出该子段起点和终点 2 { 3 int start,end,answerStart,answerEnd; 4 long long endMax,answer; 5 6 answer=a[0]; 7 answerStart=answerEnd=0; 8 endMax=a[0];start=0; 9 for(end=1;end<n;end++) 10 { 11 if(endMax<0) 12 { 13 endMax=a[end]; 14 start=end; 15 } 16 else endMax=endMax+a[end]; 17 18 if(endMax>answer) 19 { 20 answer=endMax; 21 answerStart=start; 22 answerEnd=end; 23 } 24 } 25 printf("%d %d\n",answerStart+1,answerEnd+1); 26 return answer; 27 }
