学步园

HDOJ 1003 Max Sum

/*
HDOJ 1003
求最大子序列和，简单DP
*/

#include <iostream>
using namespace std;

struct Sub_len
{
	int star;
	int end;
}s[100001];

int m[100001];
int dp[100001];

int main()
{
	int nCase,i,n,j,k,_max,_tans;
	cin>>nCase;
	for(i=1;i<=nCase;i++)
	{
		cin>>n;
		for(j=1;j<=n;j++)
			cin>>m[j];
		memset(dp,0,sizeof(dp));
		dp[1]=m[1];
		s[1].star=1;
		s[1].end=1;
		for(j=2;j<=n;j++)
		{
			if(dp[j-1]+m[j] >= m[j])
			{
				dp[j]=dp[j-1]+m[j];
				s[j].star=s[j-1].star;
				s[j].end=j;
			}
			else
			{
				dp[j]=m[j];
				s[j].star=j;
				s[j].end=j;
			}
		}
		_max= -999999;
		_tans= -1;
		for(j=1;j<=n;j++)
		{
			if(dp[j] > _max)
			{
				_max=dp[j];
				_tans=j;
			}
		}
		cout<<"Case "<<i<<":"<<endl;
		cout<<_max<<" "<<s[_tans].star<<" "<<s[_tans].end<<endl;
		if(i != nCase)
			cout<<endl;
	}
	return 0;
}