一、問(wèn)題描述

給定由n個(gè)整數(shù)組成的序列(a_1,a_2,…,a_n)，最大子段和問(wèn)題要求該序列形如

的最大值(1≤i≤j≤n)，當(dāng)序列中所有整數(shù)均為負(fù)整數(shù)時(shí)，其最大子段和為0。

例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和為：

注意：必須是連續(xù)整數(shù)的和。

二、分治策略

（1）劃分

–按照平衡子問(wèn)題的原則，將序列(

, ,…, ) 劃分成長(zhǎng)度相同的兩個(gè)子序列( ,…, )和( ,…, )，則會(huì)出現(xiàn)以下三種情況：

①

, ,…, 的最大子段和 = ,…, 的最大子段和；

②

, ,…, 的最大子段和 = ,…, 的最大子段和；

③

, ,…, 的最大子段和 = , 且1≤i≤? ? , ? ?+1≤j≤n

（2）求解子問(wèn)題

對(duì)于劃分階段的情況①和②可遞歸求解

對(duì)情況③，分別計(jì)算

則

為情況③的最大子段和。

（3）合并

–比較在劃分階段的三種情況下的最大子段和，取三者之中的較大者為原問(wèn)題的解。

步驟示意圖

三、算法實(shí)現(xiàn)

int MaxSum(int a[ ], int left, int right){sum=0;if (left= =right) { //如果序列長(zhǎng)度為1，直接求解if (a[left]>0) sum=a[left];else sum=0;}else {center=(left+right)/2; //劃分leftsum=MaxSum(a, left, center); //對(duì)應(yīng)情況①，遞歸求解rightsum=MaxSum(a, center+1, right); //對(duì)應(yīng)情況②，遞歸求解s1=0; lefts=0; //以下對(duì)應(yīng)情況③，先求解s1for (i=center; i>=left; i--) {lefts+=a[i];if (lefts>s1) s1=lefts;}s2=0; rights=0; //再求解s2for (j=center+1; j<=right; j++) { rights+=a[j];if (rights>s2) s2=rights;}sum=s1+s2; //計(jì)算情況③的最大子段和 if (sum<leftsum) sum=leftsum; //合并，在sum、leftsum和rightsum中取較大者if (sum<rightsum) sum=rightsum;}return sum; } 思考：采用分治法求解(-20,11,-4,13,-5,-2)的最大子段和, 寫(xiě)出求解過(guò)程。

四、時(shí)間復(fù)雜度分析

對(duì)應(yīng)劃分得到的情況①和②，需要分別遞歸求解；

對(duì)應(yīng)情況③，兩個(gè)并列for循環(huán)的時(shí)間復(fù)雜性是O(n)，所以，存在如下遞推式：

綜上，時(shí)間復(fù)雜性為O(nlog2n)。

內(nèi)容有待完善，請(qǐng)客官等待更新！

總結(jié)

以上是生活随笔為你收集整理的最大子序列求和_算法——求最大子段和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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