程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDOJ1231DP

HDOJ1231DP

編輯：C++入門知識

HDOJ1231DP

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;ib;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca_d(x) scanf("%d",&x)
#define Sca_s(x) scanf("%s",x)
#define Sca_c(x) scanf("%c",&x)
#define Sca_f(x) scanf("%f",&x)
#define Sca_lf(x) scanf("%lf",&x)
#define Fill(x,a) memset(x,a,sizeof(x))
#define MAXN 100005

int n;
int num[MAXN];
int before[MAXN];
int main()
{
	//input;
	int i,start,end,ans,pos,mmax;
	while(cin>>n,n)
	{
		Fill(num,0);
		Fill(before,0);
		start=end=0;
		ans=mmax=0;
		int flag=1;
		For2(i,0,n-1)
		{
			Sca_d(num[i]);
			if (num[i]>=0) flag=0;//為了判斷全是負數的情況 
			before[i]=num[i]+before[i-1];//只記錄最大值的終點位置，起點位置用前綴和搜 
			//printf("%d ",before[i]);
		}
		For2(i,0,n-1)
		{
			ans+=num[i];
			if (ans>mmax)//更新最大值 
				mmax=ans,end=num[i],pos=i;
			else if (ans<0)//如果當前加的和小於0，那麼肯定不會是最優解重新開始 
				ans=0;
		}
		if (flag)//Case1：所有的數都是負數 
			printf("0 %d %d\n",num[0],num[n-1]);
		else if (mmax==end)//Case2：一個數就是最大值
						   //為了防止第一個數就是最大數 
			printf("%d %d %d\n",mmax,end,end);
		else
		{
			For2(i,0,pos)
				if (before[pos]-before[i]==mmax)//前綴和求起始值 
				{
					start=num[i+1];
					break;
				}
			printf("%d %d %d\n",mmax,start,end);
		}
	}
	return 0;
}