【DP温习2】HDU 1003——Max Sum

【DP复习2】HDU 1003——Max Sum

题目：点击打开链接

这个问题是DP，但是不需要数组就可以做，应用startpos,endpos记录位置。tmp读数，now计算当前记录的和，判当前+读入的数是否小于读入的数，如果越读越小的话，那么就换一个位置，如果增大，说明对MAX是有利的，移动endpos就可以了，最后和maxsum进行比较。

附一组Trick数据：

5 -1 -2 -3 -4 -5答案是 -1 1 1.

#include <iostream>
using namespace std;

int main()
{
	int testcase;
	cin>>testcase;
	for(int i=1;i<=testcase;i++)
	{
		int n,tmp,tp;
		int maxnum,startpos,endpos,tstart,now;
		cin>>n>>tmp;
		startpos=1;
		endpos=1;
		tstart=1;
		maxnum=tmp;//一定要临时在这里设置一个 
		now=tmp;
		for(int j=2;j<=n;j++)
		{
			cin>>tp;
			if(now+tp<tp)
			{
				now=tp;
				tstart=j;   //临时标记的变量 
			}
			else
			{
				now+=tp;
			}
			if(now>maxnum)
			{
				maxnum=now;
				startpos=tstart;
				endpos=j; 
			}
		}
		
		cout<<"Case "<<i<<":"<<endl;
		cout<<maxnum<<" "<<startpos<<" "<<endpos<<endl;
		if(i!=testcase)
			cout<<endl;
	}
	return 0;
}