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

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;
}