Max Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 52833    Accepted Submission(s): 11726

2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Case 1:
14 1 4

Case 2:
7 1 6

#include <stdio.h><br /> int main()<br /> {int n,T,a,sta,end,max,k,i,p,t;</p> <p> scanf("%d",&T);<br /> for(p=1;p<=T;p++) {<br /> scanf("%d",&n);<br /> max=-9999; //因为一个数a 是-1000~1000的，所以这里相当于变成最小值<br /> t=0; //表示 某段连续和<br /> sta=end=k=1; // sta最大和的开始,end最大和的结束,k记录每次求和的开始<br /> for(i=1;i<=n;i++) {<br /> scanf("%d",&a); </p> <p> t+=a;<br /> if(t>max) { //记录最大连续和的值<br /> max=t;<br /> sta=k;<br /> end=i;<br /> }<br /> if(t<0) {<br /> t=0;<br /> k=i+1;<br /> }<br /> }</p> <p> if(p!=1) printf("/n");<br /> printf("Case %d:/n",p);<br /> printf("%d %d %d/n",max,sta,end);<br /> }<br /> } 

下面是用数组做的：

#include <stdio.h><br /> #include <string.h><br /> int a[100002];<br /> int t,n,max,sum,l,r,i,j,k;<br /> int main()<br /> {<br /> scanf("%d",&t);<br /> for(i=1;i<=t;i++){<br /> scanf("%d",&n);<br /> bool pd=0;<br /> sum=max=l=r=0;<br /> k=1;<br /> for(j=1;j<=n;j++) {<br /> scanf("%d",a+j);<br /> if(a[j]>0) pd=1;<br /> sum+=a[j];<br /> if(sum<0) sum=0,k=j+1;<br /> if(sum>max) max=sum,l=k,r=j;<br /> }<br /> if(!pd){<br /> max=a[1],l=1,r=1;<br /> for(j=2;j<=n;j++)<br /> if(a[j]>max)<br /> max=a[j],l=j,r=j;<br /> }<br /> printf("Case %d:/n",i);<br /> printf("%d %d %d/n",max,l,r);<br /> if(i<t) puts("");<br /> }<br /> }<br />