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

1、算法探討——再議經(jīng)典算法問題：求最大子序列和、絕對(duì)值最大子序列和以及其區(qū)間給定任一數(shù)字序列，如54201623，求出其最大子序列和，絕對(duì)值最大子序列和以及對(duì)應(yīng)的區(qū)間，在這個(gè)例子中，人肉計(jì)算可知最大子序列和為16，區(qū)間為[33)（數(shù)組下標(biāo)從0開始），而絕對(duì)值最大子序列和為21，區(qū)間為[02]，那么算法如何描述及實(shí)現(xiàn)呢？在經(jīng)典的書籍《數(shù)據(jù)結(jié)構(gòu)與算法分析C語(yǔ)言描述第2版》中，作者向我們介紹了求最大子序列和的三種算法，時(shí)間復(fù)雜度從O(N3)下降

2、到O(N)，求最大子序列和絕對(duì)值和以及其區(qū)間是我對(duì)這一問題的擴(kuò)展。一、求最大子序列和以及其區(qū)間求最大子序列和的算法相對(duì)簡(jiǎn)單，并且可以使用動(dòng)態(tài)規(guī)劃思想將其優(yōu)化至O(N)，問題的關(guān)鍵：前面已輸入的元素的計(jì)算結(jié)果并不依賴于后面的輸入。O(N2)算法：N次遍歷數(shù)組，對(duì)其中每一個(gè)元素，繼續(xù)遍歷后續(xù)每個(gè)元素，并求和，如發(fā)現(xiàn)比當(dāng)前和大，替換當(dāng)前和。CC實(shí)現(xiàn)：1intmaxsub(constinta[]intn)23intsummaxijbeginen

3、d4begin=end=max=05f(i=0imax)1415max=sum16begin=i17end=j181920printf(“the%dloopmax=%dn“i1max)2122printf(“finalBegin=%dEnd=%dn“beginend)23returnmax244begin=end=max=05f(i=0imax)1415max=abs(sum)16begin=i17end=j181920printf(“

4、the%dloopmax=%dn“i1max)2122printf(“finalBegin=%dEnd=%dn“beginend)23returnmax24O(N)算法，在竹風(fēng)撫荷塘同學(xué)的幫助下，順利求解。思路其實(shí)很簡(jiǎn)單，絕對(duì)值最大的子序列和，要么是和最大，要么是和最小，類似問題一中O(N)算法，同時(shí)求每一個(gè)輸入可能得到的最大和或最小和，再比較即可。下面是CC代碼實(shí)現(xiàn)：1intmaxAbsSubLinear(inta[]intn)23i