1. 问题描述

最大连续子序列和问题，即是求给定序列中连续元素之和的最大值，例如给定序列a为：

{ -1, 2, 3, 7, -5, 4 }

那么最大子序列之和为12，子序列为 { 2, 3, 7 }.

2. 问题分析

我们使用动态规划来解决这道题，使用动态规划的思想就是要得到该问题的状态定义和状态转移方程，状态定义可以轻松得出：

sum[ i ]：以第i个元素结尾的子序列之和 我们的目的就是要求出最大的sum[i]。还是以问题描述中的例子为例，当 i = 0 时，sum[0] = -1；当 i = 1 时，sum[1] = max{ a[1], sum[0] + a[1] } = 2；当 i = 2 时，sum[2] = max{ a[2], sum[1] + a[2] } = 5 ...... 这样我们就可以很容易地得到状态转移方程：

sum[ i ] = max{ a[ i ], sum[ i - 1 ] + a[ i ] }

根据状态转移方程，就可以容易地得到以下代码：

int max_sub(int a[], int size) { int i; int max = 0,sum = 0; for(i = 0;i < size;i++) { if(sum + a[i] < a[i]) sum = a[i]; else sum += a[i]; if(max < sum) max = sum; } return max; }