最大连续子序列和问题如下：
给定一个数字序列A1，A2，...，An，求i,j(1<=i<=j<=n)，使得Ai+...+Aj最大，输出这个最大和。
样例：
-2 11 -4 13 -5 -2
显然11+（-4）+13=20为和最大的选取情况，因此最大和为20
下面介绍动态规划的做法，复杂度为O(n)。
步骤1：令状态dp[i]表示以A[i]作为末尾的连续序列的最大和（这里是说A[i]必须作为连续序列的末尾）
步骤2：做如下考虑：因为dp[i]要求是以A[i]结尾的连续序列，那么只有两种情况：
1、这个最大和的连续序列只有一个元素，即以A[i]开始，以A[i]结尾。
2、这个最大和的连续序列有多个元素，即从前面某处A[p]开始(p<i)，一直到A[i]结尾。
对于第一种情况，最大和就是A[i]本身。
对于第二种情况，最大和是dp[i-1]+A[i]。
于是得到状态转移方程：
dp[i]=max{A[i]，dp[i-1]+A[i]}
这个式子只和i与i之前的元素有关，且边界为dp[0]=A[0]，由此从小到大枚举i，即可得到整个dp数组。接着输出dp[0]，dp[1],...,dp[n-1]中的最大值即为最大连续子序列的和。
代码如下：
/* 最大连续子序列和 */ #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <time.h> #include <stdbool.h> #define maxn 10010 int A[maxn], dp[maxn]; // A[i] 存放序列，dp[i] 存放以 A[i] 为结尾的连续序列的最大和 // 求较大值 int max(int a, int b) { return a>b ? a : b; } int main() { int n, i, k; scanf("%d", &n); for(i=0; i<n; ++i) { // 输入序列 scanf("%d", &A[i]); } dp[0] = A[0]; // 边界 for(i=1; i<n; ++i) { // 状态转移方程 dp[i] = max(A[i], dp[i-1] + A[i]); } // 求最大连续子序列和 k = dp[0]; for(i=1; i<n; ++i) { if(dp[i] > k) { k = dp[i]; } } printf("%d ", k); // 输出 return 0; }
状态的无后效性是指：当前状态记录了历史信息，一旦当前状态确定，就不会再改变，且未来的决策只能在已有的一个或若干个状态的基础上进行，历史信息只能通过已有的状态去影响未来的决策。