給出一個長度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
說明
【樣例說明】2 -4 3 -1 2 -4 3
【數據規模與約定】
對于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 }

?

總結

以上是生活随笔為你收集整理的最大连续和问题【四种不同的算法】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。