题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003

题目描述：寻找一个序列中和值最大的子段序列，例如6，-1，5，4，-7，其最大子段和为 14（6+-1+5+4）

解题思路：运用动态规划的方法，其状态转移方程为sum=sum<0?sum+a[i]:a[i](sum为累计和，如果和大于0，那么就加上当前a[i]，如果不大于0，那么直接舍弃，从a[i]开始）

并将每次的sum结果与之前的max值进行比较。

#include<stdio.h>int dp[100000];int main(){    int j, t, n, i, sum, max, st, ed, y, x;    scanf("%d", &t);    for(j=1; j<=t; j++)    {        scanf("%d", &n);        for(i=0; i<n; i++)        {            scanf("%d", &dp[i]);        }        sum = max =dp[0];        st = ed = x = y =0;         for(i=1; i<n; i++)        {            if(sum > 0)              //sum值为正值，累加，记录当前结束点ed             {                sum+=dp[i];				ed=i;                             }            if(sum <= 0)              //sum值为负或0，之前的子段已经没必要了，dp[i]作为新起点             {                sum=dp[i];                st=i;                ed=i;            }            if(sum>max)               //刷新max、st、ed             {                max=sum;                x=st;                y=ed;            }        }        printf("Case %d:\n%d %d %d\n", j, max, x+1, y+1);        if(j!=t)            printf("\n");    }    return 0;}

1231和1003基本相同

题目链接：