問題：一個有N個整數(shù)元素的一維數(shù)組，那么求子數(shù)組和的最大值。

分析：首先我們明確問題，子數(shù)組是聯(lián)系的，不用返回元素的位置，元素是整數(shù)，可能為正，負或0。我們來看看最經(jīng)典的解法：a[0],a[1]…a[N-1]，用分治的思想，a[0]和a[1]…a[N-1]，是什么關(guān)系呢？a[1]…a[N-1]，包含兩部分，1，以a[1]為開頭的最大值，2，a[1]…a[N-1]，有一個最大值，那么我們只要比較{a[0],a[0]+以a[1]開頭的最大值，a[1]…a[N-1]之間的最大值}就可以得出結(jié)果，那么a[1]與a[2]…a[N-1]呢？也一樣……a[N-2]與a[N-1]呢？代碼如下：

? void FindBigSubArray_FenZhi(int* arr, int size) {int nStart = arr[size - 1];//以arr[size - 1]開頭的最大值int nAll = arr[size - 1];//arr[size - 1]到arr[N-1]之間的最大值for (int i = size - 2; i >= 0; i--){nStart = max1(arr[i], arr[i] + nStart);//比較arr[i]與arr[i]為開頭的最大值，nStart確保永遠是以arr[i]為開頭的最大值跟arr[i]的比較nAll = max1(nStart, nAll);//得到arr[i]之后的一段數(shù)組的最大值}cout<<"max="<<nAll<<endl; }

轉(zhuǎn)載于:https://www.cnblogs.com/cluster/archive/2011/06/12/2078737.html

總結(jié)

以上是生活随笔為你收集整理的Programe_Of_Beauty：2.14 求数组的子数组之和的最大值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。