問題：一個有N個整數(shù)元素的一維數(shù)組(A[0]，A[1]，...，A[n-2]，A[n-1])，這個數(shù)組有很多子數(shù)組（連續(xù)的幾個數(shù)），那么子數(shù)組之和的最大值是什么呢？

據(jù)說微軟曾用這道題難倒很多學(xué)生，本文從《編程之美》中記錄了一種速度比較快的解法。

分析：可以考慮數(shù)組的第一個元素A[0]，假設(shè)已經(jīng)知道（A[1],...,A[n-1]）中和最大的一段數(shù)組之和為All[1]，并且已經(jīng)知道（A[1],...,A[n-1]）中包含A[1]的和最大的一段數(shù)組為Start[1]，那么，（A[0],...,A[n-1]）中問題的解All[0]是就是max{A[0]，A[0]+Start[1],All[1]}。通過這樣的分析，可以看出這個問題符合無后效性，可以使用動態(tài)規(guī)劃的方法來解決。

完整代碼如下（dev-c++環(huán)境下編譯運行）：

#define max(x, y) (x > y ? x :y)

int MaxSum(int *A, int n)
{
     // 參數(shù)檢查
     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("最大子數(shù)組和為:%d\n",MaxSum(A,6)); 
     system("pause"); 
     return 0;
}