问题：一个有N个整数元素的一维数组(A[0]，A[1]，...，A[n-2]，A[n-1])，这个数组有很多子数组（连续的几个数），那么子数组之和的最大值是什么呢？
据说微软曾用这道题难倒很多学生，本文从《编程之美》中记录了一种速度比较快的解法。
分析：可以考虑数组的第一个元素A[0]，假设已经知道（A[1],...,A[n-1]）中和最大的一段数组之和为All[1]，并且已经知道（A[1],...,A[n-1]）中包含A[1]的和最大的一段数组为Start[1]，那么，（A[0],...,A[n-1]）中问题的解All[0]是就是max{A[0]，A[0]+Start[1],All[1]}。通过这样的分析，可以看出这个问题符合无后效性，可以使用动态规划的方法来解决。
完整代码如下（dev-c++环境下编译运行）：
#define max(x, y) (x > y ? x :y)
int MaxSum(int *A, int n)
{
// 参数检查
int i = 0;
int nStart = A[n-1];
int nAll = A[n-1];
for (i = n-2; i >= 0; i--)
{
nStart = max(A[i], nStart + A[i]);
nAll = max(nStart, nAll);
}
return nAll;
}
int main()
{
int A[] = {0, -2, 3, 5, -1, 2};
printf("最大子数组和为:%d\n",MaxSum(A,6));
system("pause");
return 0;
}
