学步园

 http://acm.hdu.edu.cn/showproblem.php?pid=1003

只有这个代码能通过

/*<br /> 1003 Max Sum<br /> Time Limit : 1000 ms Memory Limit : 32768 K Output Limit : 1024 K<br /> GUN C</p> <p>input 4 -6 -8 0 -3<br /> output 0 1 1<br /> OJ有错误，连不正确的也AC<br /> */<br /> #include <stdio.h></p> <p>int input[100000];</p> <p>int main()<br /> {<br /> int i,j;<br /> int start,end;<br /> int x,y;<br /> int b;<br /> int n;<br /> int max;<br /> int cs,k;<br /> int flag;<br /> scanf("%d",&cs);<br /> for(k=1;k<=cs;k++)<br /> {<br /> printf("Case %d:/n",k);<br /> scanf("%d",&n);<br /> for(i=0;i<n;i++)<br /> scanf("%d",&input[i]);<br /> x=0;y=0;<br /> start=0;end=0;<br /> max=-10000000;<br /> b=0;<br /> flag=0;<br /> for(i=0;i<n;i++)<br /> {<br /> if(input[i]>=0)<br /> {<br /> if(flag==0)<br /> {<br /> max=0;<br /> x=i;<br /> }<br /> flag=1;<br /> }<br /> if(flag==1)<br /> {<br /> if(b+input[i]<0)<br /> {<br /> b=0;<br /> x=i+1;<br /> }<br /> else<br /> {<br /> b=b+input[i];<br /> y=i;<br /> }<br /> if(max<b)<br /> {<br /> max=b;<br /> start=x+1;<br /> end=y+1;<br /> }<br /> }<br /> else<br /> {<br /> if(max<input[i])<br /> {<br /> max=input[i];<br /> start=i+1;<br /> end=i+1;<br /> }<br /> }<br /> }<br /> printf("%d %d %d/n",max,start,end);<br /> if(k!=cs) printf("/n");<br /> }<br /> return 0;<br /> }</p> <p>

下面这两个没通过

/*<br /> 1003 Max Sum<br /> Time Limit : 1000 ms Memory Limit : 32768 K Output Limit : 1024 K<br /> GUN C</p> <p>input 4 -6 -8 0 -3<br /> output 0 3 3<br /> */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #define T 20<br /> #define N 100000</p> <p>int main()<br /> {<br /> int t,n,ca,cb,now,add,sub,flag,start,end,p1,p2;<br /> int num[N]={0};<br /> if(scanf("%d",&t)==1)<br /> {<br /> if(t>T)<br /> return 0;<br /> for(ca=0;ca<t;ca++)<br /> {<br /> printf("Case %d:/n",ca+1);<br /> scanf("%d",&n);<br /> p1=p2=start=end=flag=now=add=sub=0;<br /> for(cb=1;cb<=n;cb++)<br /> {<br /> scanf("%d",&num[cb]);<br /> switch(flag)<br /> {<br /> case 0:<br /> if(num[cb]>=0)<br /> {<br /> now+=num[cb];<br /> end=cb;<br /> if(start==0)<br /> start=cb;<br /> }<br /> else<br /> {<br /> if(end!=0)<br /> { flag=1;p1=cb;sub=num[cb];}<br /> }<br /> break;<br /> case 1:<br /> if(num[cb]>=0)<br /> {<br /> flag=2;p2=cb;<br /> add=num[cb];<br /> }<br /> else<br /> {<br /> sub+=num[cb];<br /> }<br /> break;<br /> case 2:<br /> if(num[cb]>=0)<br /> {<br /> add+=num[cb];<br /> }<br /> else<br /> {<br /> if(add+sub+now<add)<br /> {<br /> start=p2-1;<br /> end=cb-1;<br /> now=add;<br /> sub=add=0;<br /> }<br /> else<br /> {<br /> if(add+sub>0)<br /> {<br /> end=cb-1;<br /> now+=add+sub;<br /> sub=add=0;<br /> }<br /> else<br /> { end=p1-1;}<br /> }<br /> flag=1;<br /> sub=num[cb];<br /> p1=cb;<br /> }<br /> break;<br /> }<br /> }<br /> if(flag==0 && end==0)<br /> for(cb=1,start=end=1;cb<=n;cb++)<br /> {<br /> if(num[cb]>num[start])<br /> { end=start=cb;now=num[start];}<br /> }</p> <p> printf("%d %d %d/n",now,start,end);<br /> if(ca!=t-1)<br /> printf("/n");<br /> }<br /> }<br /> return 0;<br /> }<br />

下面这个代码想法很好，但是没通过

/*<br /> 1003nb Max Sum<br /> Time Limit : 1000 ms Memory Limit : 32768 K Output Limit : 1024 K</p> <p>GUN C++<br /> */<br /> #include <iostream.h><br /> using namespace std;</p> <p>const int NMAX=100000;</p> <p>int main()<br /> {<br /> int t,n,ca,cb,i,j,sum,max,now;<br /> while(cin>>t)<br /> {<br /> for(ca=1;ca<=t;ca++)<br /> {<br /> cin>>n;<br /> sum=0;max=-2147483647;<br /> for(cb=1;cb<=n;cb++)<br /> {<br /> cin>>now;<br /> sum+=now;<br /> if(sum>=0 && max<0)<br /> { i=cb;}<br /> if(sum>max)<br /> { max=sum;j=cb;}<br /> if(sum<0)<br /> { sum=0;}<br /> }<br /> cout<<"Case "<<ca<<":/n"<<max<<" "<<i<<" "<<j<<endl;<br /> if(ca!=t)<br /> cout<<endl;<br /> }<br /> }<br /> return 0;<br /> }</p> <p>

#include <iostream><br /> using namespace std;</p> <p>/*<br /> 思路:<br /> 变量start，end分别保存开始位置和结束位置，max保存上一次的最大值，sum表示当前和。<br /> （1）找到sum>=0的值，即为start的值，然后比较sum和max，<br /> （2）若sum>max,更新end的值；<br /> （3）若sum<0;则令sum＝0，从第（1）步重新开始<br /> */</p> <p>int main()<br /> {<br /> int T;<br /> cin>>T;<br /> int i, j, start, end, max, sum, temp;</p> <p> for(i=1; i<=T; i++)<br /> {<br /> int N;<br /> cin>>N;<br /> sum = 0;<br /> max = -100000000;//让max＝-100000000是用来判断 否是第一个使sum>=0的值 ,若是，则将对start赋值<br /> for(j=1; j<=N; j++)<br /> {<br /> cin>>temp;<br /> sum += temp;<br /> if(sum < 0)<br /> {<br /> sum = 0; //若sum<0,不做任何处理，进行下一位操作<br /> }<br /> if((sum >= 0) && (max < 0))<br /> {<br /> start = j;<br /> }<br /> if(sum > max)<br /> {<br /> max = sum;<br /> end = j;<br /> }<br /> }<br /> printf("Case %d:/n", i);<br /> printf("%d %d %d/n", max, start, end);<br /> if(i != T)<br /> {<br /> printf("/n");<br /> }<br /> }<br /> }<br />