问题：
1. 一个由N个整数元素的一维数组，求其所有子数组中元素和的最大值。
2. 如果数组首尾相邻，也就是允许子数组A[i],...,A[n-1],A[0],...,A[j]存在，求其所有子数组总元素和的最大值。
1. 解法：
我们使用动态规划的思想可以在O(n)的时间内计算出子数组之和最大值。
动态规划问题往往非常灵活，所以在做题的时候不知道如何编写，其实它有很清晰的分析方法，按照这个方法就可以较容易的解决动态规划的问题。具体参考IOI2000 张辰的论文《动态规划的特点及其应用》
阶段：在所有以元素k结尾的子数组中，选出元素和最大的子数组，k=1,2...n。
状态：以元素k结尾的和最大的子数组是包含以元素k-1结尾的和最大的子数组还是就只有元素k这一个元素，即有这两个可选状态。
之所以选择这样的阶段和状态，因为这种选择方式具有无后效性，即阶段k+1（以元素k+1结尾的子数组）只会与阶段k（以元素k结尾的子数组）发生关联，而与其它阶段无关。在得到以每个元素结尾的和最大的子数组之后，只要取其中最大值就是所有子数组中最大的子数组。
#include <iostream> #include <algorithm> using namespace std; #define MAXN 1003 int A[MAXN]; // 动态规划思想，时间复杂度O(n) int Tail[MAXN]; int main() { int n, i, j, k; cin >> n; for (i=1; i<=n; i++) cin >> A[i]; // 计算以k结尾的子数组之和的最大值，即子数组包含第k个数 Tail[1] = A[1]; for (k=2; k<=n; k++) // k个阶段 Tail[k] = max(A[k],Tail[k-1]+A[k]); // 只有两个状态 // 因为和最大的子数组肯定以某个数结尾，所以取这n个子数组的最大值 // 就是和最大的子数组 int All = Tail[1]; for (i=2; i<=n; i++) All = max(All, Tail[i]); cout << All; }
虽然这种标准的动态规划方法时间复杂度已经最优了，但它仍要占用O(n)的空间，对于一般的动态规划问题占用较多的空间是不可避免的，但这个问题较简单，仍可以继续优化。我们把All取最大值的操作放入Tail的计算循环中，如下：
Tail[1] = A[1]; All = Tail[1]; for (k=2; k<=n; k++)// k个阶段 { Tail[k] = max(A[k],Tail[k-1]+A[k]);// 只有两个状态 All = max(All, Tail[k]); } 由于循环体中只关心当前的Tail[k]和上一个Tail[k-1]，可以省去之前所计算出的Tail[1],Tail[2]...Tail[k-2]的数据，如下： Tail = A[1]; All = Tail; for (k=2; k<=n; k++)// k个阶段 { Tail = max(A[k],Tail+A[k]);// 只有两个状态 All = max(All, Tail); }
最后优化后的代码就是书中最后给出的结果。
2. 解法：
把问题分为两种情况：
(1)最大和子数组没有跨过A[n]到A[1]（如问题1）
(2)最大和子数组跨过A[n]到A[1]
对于情况(2)，这样的最大和子数组包含两个部分：以A[1]开始的最大和子数组，以及以A[n]结尾的最大和子数组，并且这两个子数组不允许重叠，那么将这两个子数组拼合起来就是情况(2)的解。
#include <iostream> #include <algorithm> using namespace std; #define MAXN 1003 int A[MAXN]; int main() { int n, i, j, k; cin >> n; for (i=1; i<=n; i++) cin >> A[i]; // 和最大的子数组没有跨过A[n]和A[1] int Tail = A[1]; int All = Tail; for (k=2; k<=n; k++) // k个阶段 { Tail = max(A[k],Tail+A[k]); // 只有两个状态 All = max(All, Tail); } // 和最大的子数组跨过了A[n]和A[1] int Start = A[1]; for (i=2; i<=n && Start+A[i]>Start; i++) Start += A[i]; Tail = A[n]; for (j=n-1; j>=1 && Tail+A[j]>Tail; j--) Tail += A[j]; if (i<j && Start+Tail > All) All = Start+Tail; cout << All; }