杭电ACM题1003

Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

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

  
Case 1:
14 1 4Case 2:
7 1 6这题跟我有仇哈。。。。
#include "iostream"
using namespace std ;int main()
{int a[1003];//存储输入的一些数int str[1003];//存储依次计算得到的和int start[1003];//存储序列和种最大值的最先开始元素序号int t,n;int num=1;cin>>t;while (t--)//case的次数{cin>>n;//输入n个数for(int i=1;i<=n;i++){cin>>a[i];}str[1]=a[1];start[1]=1;for (int j =2;j<= n;j++){if (str[j-1]>=0)//元素数和大于0则继续看下一位{str[j]=str[j-1]+a[j];start[j]=start[j-1];}else{//小于0从写一个元素记录开始str[j]=a[j];start[j]=j;}}int max=str[1];int end=1;//随便初始化一下for ( int k = 0; k<=n; k++)//找到序列和中的最大值{if (str[k]>max){max=str[k];end=k;}}cout<<"Case"<<" "<<num<<":"<<endl;num++;cout<<max<<" "<<start[end]<<" "<<end;if (t) cout<<endl;}return 0;
}<span style="color:#000066;">跟着学习了，原来这样才能通过杭电的编辑器</span>
#include "iostream"
using namespace std ;int main(){  int r = 0,l = 0,i= 0 ,j = 0,num =0,n,t=0;int sum = 0,max = 0; int *a;cin>>n;while(n--){cin>>num;a = (int *)calloc(num,sizeof(int));  for(i = 0; i < num ;i ++)cin>>a[i];for( l = 0,r = 0,sum = 0,max = a[0],i = 0;i <num ;i ++){for(sum = 0,j = i ;j <num ;j ++){sum += a[j];if(sum > max){max = sum ;l = i;r = j;}if(sum < 0){i = j;sum =0;break;  }  }  }  t++;cout<<"Case"<<" "<<t<<":"<<endl;cout<<max<<" "<<l+1<<" "<<r+1<<endl;if (n) cout<<endl;}system("pause");return 0;  }