学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1231

动态转移方程：f(n) = max(a, a+f(n-1));

//hdu_1231
#include <stdio.h>

int max(int a, int b)
{
	return a > b ? a : b;
}

int main()
{
//	freopen("input.txt","r", stdin);
	int arr[10001];
	int dp[10001];
	int n, i;
	int ma;
	int start, end;
	int starttmp, endtmp;
	while(scanf("%d", &n)&&n){
		for(i = 0; i < n; i ++){
			scanf("%d", &arr[i]);
			dp[i] = 0;
		}
		dp[n] = 0;
		bool f = false;
		ma = dp[n-1] = arr[n-1];
		starttmp = endtmp = start = end = arr[n-1];
		for(i = n - 2; i >= 0; i --){
			dp[i] = max(arr[i], arr[i]+dp[i+1]);
			if(dp[i] == arr[i]){
					start = end = arr[i];
			}
			else start = arr[i];
			if(ma <= dp[i]){
				ma = dp[i];
				starttmp = start;
				endtmp = end;
			}
		}
		if(ma < 0)printf("0 %d %d\n", arr[0], arr[n-1]);
		else if(ma == 0)printf("0 0 0\n");
		else
			printf("%d %d %d\n", ma, starttmp, endtmp);
	}	
	return 0;
}