首页 > 代码库 > Max Sum
Max Sum
Problem Description
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.
Input
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).
Output
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.
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
Case 1:
14 1 4
Case 2:
7 1 6
1 #include <stdio.h> 2 3 int main(){ 4 int T; 5 int n; 6 int number[100001]; 7 int i; 8 int sum; 9 int max;10 int start;11 int end;12 int time;13 int temp;14 15 16 scanf("%d",&T);17 time=1;18 19 while(T--){20 sum=0;21 max=-1000;22 start=0;23 end=0;24 temp=0;25 26 scanf("%d",&n);27 28 for(i=0;i<n;i++)29 scanf("%d",&number[i]);30 31 for(i=0;i<n;i++){32 sum+=number[i];33 34 if(sum>max){35 max=sum;36 start=temp;37 end=i;38 }39 40 if(sum<0){ //关键是这里,当求和小于0时,便把下一个数值作为开头再找最大值41 sum=0;42 temp=i+1;43 }44 }45 46 printf("Case %d:\n",time);47 time++;48 printf("%d %d %d\n",max,start+1,end+1);49 if(T!=0)50 printf("\n");51 }52 53 return 0;54 }
Max Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。