P1115 最大子段和-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

P1115 最大子段和

简介: 最大连续和问题给出一个长度n的序列:A1,A2,A3,……,An。求最大连续子段和。即:要求找到1

最大连续和问题
给出一个长度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 } 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章