http://acm.hdu.edu.cn/showproblem.php?pid=1003
给出一个包含n个数字的序列{a1，a2，..，ai，..，an}，-1000<=ai<=1000
求最大连续子段和及其起始位置和终止位置，很基础的动态规划（DP）问题，看完DP第一次做的DP题目
DP真的是一种很优美的算法，或者说思想，但是比较难理解，我对DP的理解还很浅薄
# include <stdio.h>
# define INF 1000000000 int main()
{
int Start, End, Sum, Max, Num, Flag, t, n; scanf("%d",&t);
for(int Count = 0; Count < t; Count++)
{
if(Count) printf("\n"); scanf("%d",&n); //初始化
Start = Flag = 1;//Start/End:已记录的最大连续子段得起/终点; Flag:当前子段起点
End = n;
Sum = 0;//Sum:当前子段和
Max = -INF;//Max:已记录的最大连续子段和 for(int i = 1; i <= n; i++)
{
scanf("%d",&Num);
Sum += Num; //Sum大于Max 更新当前最大连续子段信息
if(Sum >= Max)
{
Max = Sum;
Start = Flag;
End = i;
}
//* Sum小于0 Sum置0 当前子段起点标志为下一个
//因为这一步的存在 每次循环结束 Sum总是>=0
//所以Sum + Num后小于0 说明Num是负数并且其绝对值比Sum大 若把该Num纳入子段 则会导致子段不是最优
if(Sum < 0)
{
Sum = 0;
Flag = i + 1;
}
} printf("Case %d:\n", Count + 1);
printf("%d %d %d\n", Max, Start, End);
} return 0;
}