﻿ ACM 1003 ：Max sum 求相邻数最大和_OC/C/C++_开心洋葱网
• 欢迎访问开心洋葱网站，在线教程，推荐使用最新版火狐浏览器和Chrome浏览器访问本网站，欢迎加入开心洋葱` QQ群`
• 为方便开心洋葱网用户，开心洋葱官网已经开启复制功能！
• 欢迎访问开心洋葱网站，手机也能访问哦~欢迎加入开心洋葱多维思维学习平台` QQ群`
• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~！
• 由于近期流量激增，小站的ECS没能经的起亲们的访问，本站依然没有盈利，如果各位看如果觉着文字不错，还请看官给小站打个赏~~~~~~~~~~~~~！

# ACM 1003 ：Max sum 求相邻数最大和

2681次浏览

ACM 1003 ：Max sum 求相邻数最大和

Problem&nbspDescription

Given&nbspa&nbspsequence&nbspa[1],a[2],a[3]……a[n],&nbspyour&nbspjob&nbspis&nbspto&nbspcalculate&nbspthe&nbspmax&nbspsum&nbspof&nbspa&nbspsub-sequence.&nbspFor&nbspexample,&nbspgiven&nbsp(6,-1,5,4,-7),&nbspthe&nbspmax&nbspsum&nbspin&nbspthis&nbspsequence&nbspis&nbsp6&nbsp+&nbsp(-1)&nbsp+&nbsp5&nbsp+&nbsp4&nbsp=&nbsp14.

&nbsp

Input

The&nbspfirst&nbspline&nbspof&nbspthe&nbspinput&nbspcontains&nbspan&nbspinteger&nbspT(1&nbsp

Output

For&nbspeach&nbsptest&nbspcase,&nbspyou&nbspshould&nbspoutput&nbsptwo&nbsplines.&nbspThe&nbspfirst&nbspline&nbspis&nbsp”Case&nbsp#:”,&nbsp#&nbspmeans&nbspthe&nbspnumber&nbspof&nbspthe&nbsptest&nbspcase.&nbspThe&nbspsecond&nbspline&nbspcontains&nbspthree&nbspintegers,&nbspthe&nbspMax&nbspSum&nbspin&nbspthe&nbspsequence,&nbspthe&nbspstart&nbspposition&nbspof&nbspthe&nbspsub-sequence,&nbspthe&nbspend&nbspposition&nbspof&nbspthe&nbspsub-sequence.&nbspIf&nbspthere&nbspare&nbspmore&nbspthan&nbspone&nbspresult,&nbspoutput&nbspthe&nbspfirst&nbspone.&nbspOutput&nbspa&nbspblank&nbspline&nbspbetween&nbsptwo&nbspcases.

&nbsp

Sample&nbspInput

2

5&nbsp6&nbsp-1&nbsp5&nbsp4&nbsp-7

7&nbsp0&nbsp6&nbsp-1&nbsp1&nbsp-6&nbsp7&nbsp-5

&nbsp

Sample&nbspOutput

Case&nbsp1:

14&nbsp1&nbsp4

Case&nbsp2:

7&nbsp1&nbsp6

C语言，使用结构体

```
#include<stdio.h>
struct T
{
int st,en,nu;
}max[100005];

int main()
{
int t,n,temp,k,i,m;
scanf("%d",&t);
k=0;
while (t--)
{
k++;
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&max[i].nu);
max[i].st=max[i].en=i;
}
temp=max[1].nu;m=1;
for (i=2;i<=n;i++)
{
if (max[i-1].nu>=0)
{
max[i].nu+=max[i-1].nu;
max[i].st=max[i-1].st;
}
if (max[i].nu>temp)
{
temp=max[i].nu;
m=i;
}
}
printf("Case %d:\n%d %d %d\n",k,temp,max[m].st,max[m].en);
if (t!=0)
{
printf("\n");
}

}
return 0;
}

```

C语言使用数组实现

```
#include<stdio.h>
int main()
{
int t,n,i,j,k,ia[100005],ib[100005],k1,k2,d,s;
scanf("%d",&t);
d=1;
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&ia[i]);
ib[i]=i;
}

k=ia[1];k1=1;k2=1;
for(i=2;i<=n;i++)
{
if(ia[i-1]>=0)
{
ia[i]+=ia[i-1];
ib[i]=ib[i-1];
}
if(ia[i]>k)
{
k=ia[i];
k2=i;
}
}
printf("Case %d:\n%d %d %d\n",d,k,ib[k2],k2);
d++;
if(t!=0)
printf("\n");
}
return 0;
}

```

C语言代码，来自：http://blog.csdn.net/iori31/

```
#include<stdio.h>
int b,e,i,k,t,n,a,s[100001],m;
int main(){
for(scanf("%d",&t),k=1;k<=t;++k){
for(scanf("%d%d",&n,&a),m=s[0]=a,e=0,i=1;i<n;++i){
scanf("%d",&a);
if(s[i-1]>=0&&s[i-1]+a>=0)s[i]=s[i-1]+a;
else s[i]=a;//s[i-1]<0时 无论a(可看作a[i])值多少 s[i]=a都合理 而且s再加上之前的和不可能成为最大值
if(s[i]>m)m=s[i],e=i;//若出现多个最大值 end始终在第一个
}
for(i=e;i>=0;--i)
if(s[i]<0)break;//若找不到s<0，任何情况都b=0
b=m>=0?i+1:i,e++,b++;//being和end自增后可直接输出 m<0必有b=e
printf("Case %d:\n%d %d %d\n%s",k,m,b,e,k<t?"\n":"");
}
}

```

C++代码，Crazy_Frog提供

```
#include <iostream>
using namespace std;
void main()
{
int n,c,num,begpos,endpos,p,sum,maxsum;
int i, j;
cin>>n;
for(i=1;i<=n;i++)
{
begpos=1;
endpos=1;
p=1;
sum=0;
maxsum=-1000;
cin>>c;
for(j=1;j<=c;j++)
{
cin>>num;
sum+=num;
if(sum>maxsum)
{
maxsum=sum;
begpos=p;
endpos=j;
}
if(sum<0)
{
p=j+1;
sum=0;
}
}
cout<<"Case "<<i<<":"<<endl;
cout<<maxsum<<" "<<begpos<<" "<<endpos;
if(i==n) cout<<endl;
else cout<<endl<<endl;
}
}

```

C++代码2

```
#include <iostream>
using namespace std;

int max_sum(int* data, int n, int& s, int& e)
{
int ans = -2147483640, curr = 0;
int start = 0, end = 0;
for (int i = 0, j = 0; i < n; ++i)
{
curr += data[i];
if (curr > ans) ans = curr, s = j, e = i;
if (curr < 0) curr = 0, j = i + 1;
}
return ans;
}

int data[100005];
int main()
{
int cas;scanf("%d", &cas);
for (int curr = 1;  curr <= cas; ++curr)
{
if (curr > 1) puts("");
int n, s, e;scanf("%d", &n);
for (int i = 0; i < n; ++i)scanf("%d", data+i);
printf("Case %d:\n%d", curr, max_sum(data, n, s, e));
printf(" %d %d\n", s+1, e+1);
}
return 0;
}
```

[开心洋葱]

• 版权声明

本站的文章和资源来自互联网或者站长的原创，按照 CC BY -NC -SA 3.0 CN协议发布和共享，转载或引用本站文章应遵循相同协议。如果有侵犯版权的资源请尽快联系站长，我们会在24h内删除有争议的资源。
• 合作网站

• 友情链接

• 关于我们

一群热爱思考，热爱生活，有理想的新社会主义接班人的多维思维学习平台，天行健，君子以自强不息。地势坤，君子以厚德载物。
……