Max Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 323149 Accepted Submission(s): 76859

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

传送门：hdu1003

一道经典的 dp 求最大子段和问题。

我们可以用 dp[i] 来表示以 I 结尾的最大子段和，所以状态转移方程为dp[i]=max(dp[i-1]+a[i],a[i])

这道题和经典的求最大子段和一样，但是增加了一个要求的问题，就是求出最大子段和的同时，求出起点和终点。

唉，这道题和博主ACM新生赛的一道题一模一样，但是当时直接用了O(n^2)的方法求，想卡卡数据，万一A了呢，但是居然没有T，一直WA。。。。。。。难受，今天又碰到了，不由感叹，为什么当时就不多想想呢，唉！！！！！！！

如果按照刚刚写那个状态转移方程，再求最大子段和的同时，如果当前的 dp[i] 大于前面的最大子段和 res,我们可以记录当前的res是以 i 结尾的，那么我们用O(n)扫一遍原数组，知道连续子段和为res时，当时的 i 就是我们的起点。但是这是错的，为什么呢？因为题目是要求，如果有多个res值一样，输出第一个，我们这样并不能保证是第一个，所以我们改变一下dp[i]的含义就行，dp[i]表示 i 开始的最大子段和，这样每次维护起点就行了。

#include<bits/stdc++.h>
using namespace std;
int T,n,a[100010],f[100010],res,l,r;
int main()
{
	cin>>T;
	for(int C=1;C<=T;C++)
	{
		printf("Case %d:\n",C);
		memset(f,0,sizeof(f));
		memset(a,0,sizeof(a));
		cin>>n;
		for(int i=1;i<=n;i++)	cin>>a[i];
		res=f[n]=a[n];
		l=n;
		for(int i=n-1;i>=1;i--)
		{
			f[i]=max(f[i+1]+a[i],a[i]);
			if(f[i]>=res)	res=f[i],l=i;
		}
		int sum=0;
		for(int i=l;i<=n;i++)
		{
			sum+=a[i];
			if(sum==res)
			{
				r=i;
				break;
			}
		}
		cout<<res<<' '<<l<<' '<<r<<endl;
		if(C!=T)	cout<<endl;	
	}
	return 0;
}