求数组的子数组之和的最大值

问题：一个有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;
}