算法探討——再議經(jīng)典算法問(wèn)題：求最大子序列和、絕對(duì)值最大子序列和以及其區(qū)間.docx

算法探討再議經(jīng)典算法問(wèn)題：求最大子序列和、絕對(duì)值最大子序列和以及其區(qū)間給定任一數(shù)字序列，如-5,4,-20,16,-2,-3，求出其最大子序列和，絕對(duì)值最大子序列和以及對(duì)應(yīng)的區(qū)間，在這個(gè)例子中，人肉計(jì)算可知最大子序列和為16，區(qū)間為3,3)（數(shù)組下標(biāo)從0開始），而絕對(duì)值最大子序列和為-21，區(qū)間為0,2，那么算法如何描述及實(shí)現(xiàn)呢？在經(jīng)典的書籍?dāng)?shù)據(jù)結(jié)構(gòu)與算法分析 C語(yǔ)言描述第2版中，作者向我們介紹了求最大子序列和的三種算法，時(shí)間復(fù)雜度從O(N3)下降到O(N)，求最大子序列和絕對(duì)值和以及其區(qū)間是我對(duì)這一問(wèn)題的擴(kuò)展。一、求最大子序列和以及其區(qū)間求最大子序列和的算法相對(duì)簡(jiǎn)單，并且可以使用動(dòng)態(tài)規(guī)劃思想將其優(yōu)化至O(N)，問(wèn)題的關(guān)鍵：前面已輸入的元素的計(jì)算結(jié)果并不依賴于后面的輸入。O(N2)算法：N次遍歷數(shù)組，對(duì)其中每一個(gè)元素，繼續(xù)遍歷后續(xù)每個(gè)元素，并求和，如發(fā)現(xiàn)比當(dāng)前和大，替換當(dāng)前和。C/C+實(shí)現(xiàn)： 1 int maxsub(const int a,int n) 2 3 int sum, max, i, j, begin, end; 4 begin = end = max = 0; 5 for(i = 0;i n;i+) 6 7 sum = 0; 8 for(j = i;j max)14 15 max = sum;16 begin = i;17 end = j;18 19 20 printf(the %d loop max = %dn,i+1,max);21 22 printf(-final- Begin = %d, End = %dn,begin,end);23 return max;24 循環(huán)結(jié)束后，begin與end的值即對(duì)應(yīng)的區(qū)間。O(N)算法：動(dòng)態(tài)規(guī)劃思想，也稱on-line algorithm，即，對(duì)于每一個(gè)輸入，不依賴于后面輸入，對(duì)每一個(gè)輸入，立即計(jì)算其結(jié)果，并保存，然后與后續(xù)輸入進(jìn)行比較，若和變大，產(chǎn)生更新。若和總是變小，丟棄之前的輸入。C/C+實(shí)現(xiàn)：int maxsublinear(const int a, int n) int i; int curSum = 0; /* 當(dāng)前序列和 */ int maxSum = 0; /* 最大序列和 */ int begin = end = 0; /* 開始循環(huán)求子序列和 */ for (i = 0; i maxSum) maxSum = curSum; end = i; /* 動(dòng)態(tài)規(guī)劃部分，舍棄當(dāng)前和為負(fù)的子序列 */ if (curSum = n ? i : i + 1; return maxSum;二、求絕對(duì)值最大子序列和以及對(duì)應(yīng)的區(qū)間這個(gè)問(wèn)題是對(duì)第一個(gè)問(wèn)題的擴(kuò)展，但比第一個(gè)問(wèn)題復(fù)雜的多，O(N2)算法基本相同，也容易理解。O(N2) C/C+實(shí)現(xiàn)： 1 int maxabssub(const int a,int n) 2 3 int sum, max, i, j, begin, end; 4 begin = end = max = 0; 5 for(i = 0;i n;i+) 6 7 sum = 0; 8 for(j = i;j max)14 15 max = abs(sum);16 begin = i;17 end = j;18 19 20 printf(the %d loop max = %dn,i+1,max);21 22 printf(-final- Begin = %d, End = %dn,begin,end);23 return max;24 O(N)算法，在竹風(fēng)撫荷塘同學(xué)的幫助下，順利求解。思路其實(shí)很簡(jiǎn)單，絕對(duì)值最大的子序列和，要么是和最大，要么是和最小，類似問(wèn)題一中O(N)算法，同時(shí)求每一個(gè)輸入可能得到的最大和或最小和，再比較即可。下面是C/C+代碼實(shí)現(xiàn)： 1 int maxAbsSubLinear(int a, int n) 2 3 int posiSum, negaSum, curSum, max, j, begin, end, posiBegin, posiEnd, negaBegin, negaEnd, flag; 4 posiSum = negaSum = curSum = max = j = begin = end = posiBegin = posiEnd = negaBegin = negaEnd = flag = 0; 5 6 for(j = 0;j aj) 9 10 posiSum += aj;11 12 else13 14 posiSum = aj;15 posiBegin = j;16 17 if(negaSum + aj abs(negaSum) )28 29 curSum = abs(posiSum);30 posiEnd = j;31 flag = 1;32 33 else34 35 curSum = abs(negaSum);36 negaEnd = j;37 flag = 0;38 39 40 if(curSum max)41 42 max = curSum;43 if(flag)44 45 begin = posiBegin;46 end = posiEnd;47 48 else49 50 begin = negaBegin;51 end = negaEnd;52 53 54 55 printf(IN ABS LINEAR - LOOP %d, posiSum = %d, negaSum = %d, curSum = %d, max=%d, begin = %d, end = %dn, j+1, p