Max Sum

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 344507 Accepted Submission(s): 81909

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

题目大意：
给你一个长度为n的int序列要你求出子序列的最大和以及他的起点和终点。
思路：
在求起点和终点之前先求子序列最大和。
定义dp[i]表示在长度1 - i 中序列的最大值。
得出状态转移方程 dp[i] = max(dp[i-1]+a[i],a[i])
最后找出dp数组中最大值就是最长子序列的和。
然后求序列的起止下标，易发现子序列最大和最后一定会落在i上，所以只需要提前求出dp[i]前面有多少个数，记录一下。然后终点-dp[i]前面个数+1=起点。。。。（可能说的不太明白，具体看代码吧）。
注意一下-1000<=a[i]<=1000
考虑全负数的时候，ans取小于-1000才行。
Ac代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=1e5+10;
struct node{
	int s,c;
}dp[maxn];
int a[maxn];
int main(){
	int T;scanf("%d",&T);
	bool flag=false;
	int k=1;
	while(T--){
		memset(dp,0,sizeof(dp));
		int n;scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		int cnt=1;
		for(int i=1;i<=n;i++){
			if(a[i]>dp[i-1].s+a[i])cnt=1;
			dp[i].s=max(dp[i-1].s+a[i],a[i]);
			dp[i].c=cnt;
			cnt++;
		}
		int ans=-2000;int start,end;
		for(int i=1;i<=n;i++){
			if(dp[i].s>ans){
				end=i;start=i-dp[i].c+1;
				ans=dp[i].s;
			}
		}
		if(flag)printf("\n");flag=true;
		printf("Case %d:\n%d %d %d\n",k++,ans,start,end);
	}
}