(hdu step 3.2.1)Max Sum(简单dp:求最大子序列和、起点、终点)

题目：

题目分析：

               简单DP。这道题是求最大子序列的和，并且要求最大子序列的起点和终点。如果不需要求起点和终点的话。直接可以有last = max(0,last) + a[i]; ans = max(last,ans)来求解即可。但，其实就算要求起点和终点，思路还是一样的这是只不过不能就直接max(0,last)。应该把这个逻辑展开，求产生当前最大序列和的起点和终点。

代码如下：

/*
 * a1.cpp
 *
 *  Created on: 2015年2月6日
 *      Author: Administrator
 */


#include <iostream>
#include <cstdio>


using namespace std;




int main(){
	int t;
	scanf("%d",&t);
	int k;
	for(k = 1 ; k <= t ; ++k){
		int n;
		scanf("%d",&n);

		int start = 1;//最大子序列和的起点.默认为1
		int end = 1 ;//最大子序列和的终点.默认为1.
		int thisSum = 0;//当前子序列的和
		int maxSum = -100005;//最大子序列的和
		int index = 1;//当前子序列的起点

		int i;
		int temp;
		for(i = 1 ; i <= n ; ++i){
			scanf("%d",&temp);

			thisSum += temp;//当前子序列的和不断地增加

			if(thisSum > maxSum){//如果当前子序列的和>最大子序列和
				maxSum = thisSum;//更新最大子序列和
				start = index;//将最大子序列的起点更新为当前子序列的起点
				end = i;//将最大子序列的终点更新为当前遍历到的这个数(因为这个数产生了目前最大的子序列和)
			}//需要注意的是,就算thisSum并没有比maxSum要大.这时候序列并没有断,要看一下后面是否会回升

			/**
			 * 需要注意的是,前面不要把这两个if语句写成
			 * if(){
			 * }else if(){
			 * }的结构
			 *
			 * 因为thisSum < maxSum && thisSum < 0 的情况是存在的
			 */
			if(thisSum < 0){//如果后面没有回升,相反已经<0了
				thisSum = 0;//断开原来的子序列,重新记数
				index = i+1;//更新当前子序列的起点
			}
		}

		printf("Case %d:\n",k);
		printf("%d %d %d\n",maxSum,start,end);
		if(k != t){
			printf("\n");
		}
	}

	return 0;
}