HDU 1003 最长字段跟(经典动态规划)

HDU 1003 最长字段和(经典动态规划)

//原来做这道题，使用刘汝佳书上的方法实现，动态规划来做，很经典的一道题

#include <cstdio>
const int nMax = 100007;

struct Node
{
	int l, r;
	int sum;
	Node(){}
	Node(int l, int r, int sum):l(l), r(r), sum(sum){}
}node[nMax];


int main()
{
	int T;
	scanf("%d", &T);
	int cas;
	for(cas = 1; cas <= T; cas ++)
	{
		int N;
		scanf("%d", &N);
		int i;
		node[0].sum = -0x3fffffff;
		for(i = 1; i <= N; ++ i)
		{
			int x;
			scanf("%d", &x);
			node[i] = Node(i, i, x);
			if(node[i - 1].sum + x >= node[i].sum)
			{
				node[i] = Node(node[i - 1].l, i, node[i - 1].sum + x);
			}
		}
		int _max = 0;
		for(i = 1; i <= N; ++ i)
			if(node[i].sum > node[_max].sum)
				_max = i;
		printf("Case %d:\n", cas);
		printf("%d %d %d\n", node[_max].sum, node[_max].l, node[_max].r);
		if(cas != T) printf("\n");
	}
	return 0;
}