求最大字段和的算法很好的講解了算法設(shè)計(jì)技術(shù)。根據(jù)《編程珠璣》上的描述，簡(jiǎn)單實(shí)現(xiàn)各種不同的算法。如下：

1、最簡(jiǎn)單的方法：對(duì)所有滿足0≤i≤j<n的(i,j)整數(shù)進(jìn)行迭代。對(duì)每個(gè)整數(shù)對(duì)，都計(jì)算x[i..j]的總和：

簡(jiǎn)單方法 int maxSum_easy(int n, int* a, int& besti, int& bestj) //最簡(jiǎn)單的方法，復(fù)雜度為O(n^3) {int maxSoFar = 0, i = 0, j = 0, k = 0, sum = 0;for (i = 0; i < n; ++i)for ( j = i; j < n; ++j){sum = 0;for (k = i; k<=j; ++k)sum += *(a+k);if (sum > maxSoFar){maxSoFar = sum;besti = i;bestj = j;}}return maxSoFar; }

2、改進(jìn)簡(jiǎn)單的方法，將復(fù)雜度變?yōu)镺(n²),注意子和求解過程，分別有兩種改進(jìn)方法：

　　方法一，如下：　

改進(jìn)一 int maxSum_O2na(int n, int *a, int& besti, int& bestj)//改進(jìn)上一算法，時(shí)間復(fù)雜度變?yōu)镺(n^2) {int maxSoFar = 0, i = 0, j = 0, k = 0, sum = 0;for (i = 0; i < n; ++i){sum = 0;for (j = i; j < n; ++j){sum += *(a+j);if (sum > maxSoFar){maxSoFar = sum;besti = i;bestj = j;}}}return maxSoFar; }

　　方法二，如下：

改進(jìn)二 int maxSum_O2nb(int n, int *a, int& besti, int& bestj) //增加一累加數(shù)組，時(shí)間復(fù)雜度變?yōu)镺(n^2) {int maxSoFar = 0, i = 0, j = 0, sum = 0;int * acc = new int[n+1]; //創(chuàng)建一個(gè)額外的累加器*(acc) = 0;for (i = 1; i <= n; ++i)*(acc+i) = * (acc+i-1) + *(a+i-1);for (i = 0; i < n; ++i)for (j = i; j < n; ++j){sum = *(acc+j+1) - *(acc+i); // sum is sum of a[i..j]if (sum > maxSoFar){maxSoFar = sum;besti = i;bestj = j;}}delete acc;return maxSoFar; }

3、同時(shí)，還可以利用分治法對(duì)其進(jìn)行求解，復(fù)雜度為O(nlogn)代碼如下：

分治法求解 int maxSum_ConDiv(int *a, int left, int right)//分治法,復(fù)雜度為O(nlogn),調(diào)用形式為maxSum_ConDiv(a,0,n-1) {int maxSoFar = 0, sum = 0, i = 0, m = (left+right)/2, lmax =0, rmax = 0, lsub = 0, rsub =0;if (left > right) //zero elementsreturn 0;if (left == right) //one elementreturn left > 0 ? left : 0;for (i = m; i >= left; --i){sum += *(a+i);if (sum > lmax)lmax = sum;}sum = 0;for (i = m+1; i <= right; ++i){sum += *(a+i);if (sum > rmax)rmax = sum;}//find max value among the 3 values and return itlsub = maxSum_ConDiv(a,left,m);rsub = maxSum_ConDiv(a,m+1,right);maxSoFar = lmax + rmax;if (lsub > maxSoFar)maxSoFar = lsub;if (rsub > maxSoFar)maxSoFar = rsub;return maxSoFar; }

4、另外一種方法，是效率最高的，復(fù)雜度為O(n)，利用了動(dòng)態(tài)規(guī)劃的思想，代碼如下：

動(dòng)態(tài)規(guī)劃求解 int maxSum_sm(int* a, int n) //掃描算法，時(shí)間復(fù)雜度為O(n) {int maxSoFar = 0, maxendinghere = 0, i =0, temp =0;for (; i < n; ++i){maxendinghere = maxendinghere+a[i];maxendinghere = maxendinghere > 0 ? maxendinghere : 0;if (maxendinghere > maxSoFar)maxSoFar = maxendinghere;}return maxSoFar; }

測(cè)試實(shí)驗(yàn)如下所示：

int main() {int a[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84},n, besti = 0, bestj = 0, maxSum = 0;n = sizeof(a)/sizeof(a[0]);cout << "a的最大子和為：" << maxSum_sm(a,n) << endl;//cout << ";是 " << besti << "->" << bestj << "的和" << endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lyfruit/archive/2013/04/15/3021317.html

總結(jié)

以上是生活随笔為你收集整理的最大字段和各种不同算法实现（参考编程珠玑）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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