Max Sum

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87125#problem/A

题意：

输入一组数，找出连续子序列中，最大的和。并输出和最大的子序列的首位置和末位置。

案例：

input

5 6 -1 5 4 -7

7 0 6 -1 1 -6 7 -5

output

Case 1：

14 1 4

Case 2：

7 1 6

思路分析：

让所有数从头开始相加，当和为负数时，只会让和变小，这时和清零，以下一个位置为起点再相加。找到最大和。

源代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #define MAX 100005
 4 using namespace std;
 5 int main()
 6 {
 7     int T,N,t=1,x,y,maxn,sum,k,s[MAX];
 8     scanf("%d",&T);
 9     while(T--)
10     {
11         int i;
12         scanf("%d",&N);
13         for(i=1;i<=N;i++)
14             scanf("%d",&s[i]);
15         x=1;y=1;maxn=-9999;sum=0;k=1;       //maxn一定要足够小
16         for(i=1;i<=N;i++)
17         {
18             sum+=s[i];
19             if(sum>maxn)
20             {
21                 maxn=sum;
22                 x=k;
23                 y=i;
24             }
25             if(sum<0)
26             {
27                 sum=0;
28                 k=i+1;       //确定新的起点
29             }
30         }
31         printf("Case %d:
%d %d %d
",t++,maxn,x,y);
32         if(T)printf("
");
33     }
34     return 0;
35 }