杭电 acm 1003 max sum 问题，求解析
这个题我没有思路，就上网上找了一个代码，ac了，但是事实上我还不明白为什么这么做，我主要有两点疑惑：1.为什么代码里要设sum和max的初始值为-1000。2.为什么代码里的if(sum>=0)
{
kj++;
sum += m;
}
else
{
ki = i;
kj = i;
sum = m;
}
这部分代码要以sum>=0和sum<0为判断条件。
Max Sum
Time Limit: 2000MS Memory limit: 32768K
题目描述
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 4
Case 2:
7 1 6
Time Limit: 2000MS Memory limit: 32768K
题目描述
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 4
Case 2:
7 1 6
程序代码：#include<stdio.h>
int main()
{
int t,n,i,max,m,sum,ki,kj,k,a,b;
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%d",&n);
max = -1000;
sum = -1000;
a = b = 1;
ki = kj = 1;
// printf("max=%d sum=%d\n",max,sum);
for(i=1;i<=n;i++)
{
scanf("%d",&m);
if(sum>=0)
{
kj++;
sum += m;
}
else
{
ki = i;
kj = i;
sum = m;
}
//printf("ki=%d kj=%d a=%d b=%d sum=%d max=%d\n",ki,kj,a,b,sum);
if(max<sum)
{
max = sum;
a = ki;
b = kj;
}
// printf("ki=%d kj=%d a=%d b=%d sum=%d max=%d\n\n",ki,kj,a,b,sum,max);
}
if(k==1) printf("Case %d:\n%d %d %d\n",k,max,a,b);
else printf("\nCase %d:\n%d %d %d\n",k,max,a,b);
}
return 0;
}
