这次看了这题的动态规划写法，顿时觉得好理解多了。

这里要对dp[i]的意义进行一下说明，dp[i]表示从1～i包含第i个数的最大子串和，如果前i-1个数的包含i-1在内的最大和为正数的话，那么包含第i个数的最大子串和就是dp[i-1]+seq[i]，否则dp[i] 就等于seq[i]了。

该题的动态递归写法并没有直接给出最终答案的状态，但是却能够根据另外的状态推到出答案。这点值得我们思考。

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define MAXN 100005using namespace std;int N, dp[MAXN], seq[MAXN], p[MAXN], begin, end;inline int max(int x, int y){    return x > y ? x : y;}void DP(int &Max){    memset(dp, 0, sizeof (dp));    dp[1] = seq[1];    Max = dp[1];    begin = end = 1;    for (int i = 2; i <= N; ++i) {        dp[i] = max(dp[i-1]+seq[i], seq[i]);        if (dp[i-1] >= 0) {            p[i] = p[i-1];        }        if (Max < dp[i]) {            begin = p[i];            end = i;            Max = dp[i];        }    }}int main(){     int T, ans;    scanf("%d", &T);    for (int ca = 1; ca <= T; ++ca) {        scanf("%d", &N);        for (int i = 1; i <= N; ++i) {            scanf("%d", &seq[i]);            p[i] = i;        }         printf("Case %d:\n", ca);        DP(ans);        printf("%d %d %d\n", ans, begin, end);        if (ca != T) {            puts("");        }    }    return 0;}