亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

基本算法-求最大子數組和 及其變種

系統 1901 0

? 這是個非常常見的算法題,見諸于《編程之美》、《編程珠璣》等經典算法書籍(亦或,經典面試書籍:))。網上有很多關于這個問題的討論和實現,我謹在此寫下自己的理解,可能之前有人寫過,但畢竟是自己思考出來的東西,權當記錄一下。

? 問題:一個有N個整數元素的一維數組(A[0],A[1].....,A[n-1]),這個數組當然有很多個子數組(n*n個),求最大的子數組之和。

? 經典解法:

      
        1
      
       maxsofar=
      
        0
      
      
        2
      
         maxendinghere=
      
        0
      
      
        3
      
      
        for
      
       i=[
      
        0
      
      
        ,n)

      
      
        4
      
           maxendinghere=max(maxendinghere+a[i],
      
        0
      
      
        )

      
      
        5
      
           maxsofar=max(maxendinghere,maxsofar)
    

? 在此我寫的是《編程珠璣》上的偽代碼,我認為這個偽代碼以及Bentley的解釋最好的詮釋了這個問題。

? Bentley寫到: The key to understanding this program is the variable maxendinghere.這個算法是典型的動態規劃算法,表述如下:

? 我們在計算前i個數的最大子數組和時,先記錄前i-1個數的最大子數組之和Max i-1 。當我們遇到新的數A[i]時,如果A[i]的加入會使得某個子數組的和大于前i-1個數的最大子數組和,則更新Max i =該子數組的和,否則,Max i =Max i-1 .接下來我們只需要考慮,A[i]的加入可能會使哪個子數組的和增加?當然是以i-1個數結尾的子數組。所以,在計算前i個數的最大子數組之和時,我們除了要記錄前i-1個數的最大子數組之和,還應該記錄以i-1個數結尾的最大子數組之和。算法如下:

? 假設我們已經知道了前i-1個數組的最大子數組為A[j],....,A[k],其和為Sum k ,同時我們記錄以i-1為結尾的最大子數組為A[m],...,A[i-1],其和為Sum i-1 ,顯然,Sum i-1 <=Sum k

? 當遇到第i個數時,如果A[i]>0,則Sum i-1 +A[i]可能會大于Sum k .所以我們更新前i個數的最大子數組之和為:max{Sum i-1 +A[i],Sum k }.

? 然后我們還應該更新以i結尾的最大子數組之和:Sum i =max{Sum i-1 +A[i],0}.亦即,如果Sum i-1 +A[i]大于0,則以i結尾的最大子數組為A[m],...,A[i-1],A[i]。否則,若Sum i-1 +A[i]小于等于0,則該子數組的和還不如一個空的子數組的和0,將該子數字重置為空,其和為0.


? 這個經典問題有一個很類似的變種:即同樣給定一個數組,寫一個在其中找出不連續子數組和的最大值,也就是說子數組里的任意相鄰的兩個元素,在原數組里都必須是不相鄰的才行。同樣以數組{1, -2, 3, 5, -1, 2}為例,則和最大的不連續子數組是{1, 5, 2},函數返回值是8。

? 有了第一個問題的解答,第二個問題應該很簡單。我們考慮下,假設我們已經知道了前i-1個數的數組的不連續子數組和的最大值,當第i個數加入時,這個不連續子數組和在什么情況下會改變?

? 第i個數加入后不能與以i-1結尾的最大不連續子數組連接,這樣會違反不連續的規則。所以我們要考慮結尾最大為i-2的和最大的不連續子數組,設其和為Sum i-2 .當Sum i-2 +A[i]大于以第i-1個數結尾的不連續子數組和的最大值時,我們更新前i個數組成的數組的不連續子數組和的最大值為Sum i-2 +A[i]。算法的代碼為:

      
        1
      
      
        for
      
      (
      
        int
      
       i=2;i<length;i++
      
        ){            

      
      
        2
      
           maxendingi=max(maxendingi_2+
      
        array[i],maxendingi_2,maxendingi_1);

      
      
        3
      
      
        int
      
       tmp=
      
        maxendingi_2;

      
      
        4
      
           maxendingi_2=
      
        max(maxendingi_1,maxendingi_2);

      
      
        5
      
      
        maxendingi_1=max(tmp+array[i],array[i]);

      
      
        6
      
       }
    

?? 其中maxendingi表示前i個數組成的數組的最大不連續子數組的和。

? maxendingi_2記錄的是結尾最大為i-2的和最大的不連續子數組的和,初始化為array[1]。

? maxendingi_1記錄的是以i-1結尾的最大的不連續子數組的和,初始化為array[2]。

? 數組長度小于3的情況可以另行處理。

參考文獻:

? [1] Jon Bentley 編程珠璣 p81

? [2] 面試趣題:求不連續子數組最大和的值

基本算法-求最大子數組和 及其變種


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦?。?!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产原创麻豆精品视频 | 免费观看一级欧美大 | 久久激情综合网 | 免费观看黄色a一级录像 | 800玖玖爱在线观看香蕉 | 国产亚洲欧美成人久久片 | 亚洲午夜天堂 | 成人精品视频一区二区在线 | a高清免费毛片久久 | 亚洲射图 | 午夜免费福利不卡网址92 | 中文婷婷 | 成人国产精品免费视频不卡 | 男人叼女人的痛爽视频免费 | 变态 调教 视频 国产九色 | 国产美女a做受大片免费 | 久久精品只有这里有 | 亚洲欧美综合 | 一级毛片免费 | 亚洲人成毛片线播放 | 久久精品亚洲综合一品 | 精品外国呦系列在线观看 | 日本久久综合视频 | 亚洲国产成人精品区 | 综合国产福利视频在线观看 | 97人人插| 久久精品亚瑟全部免费观看 | 国产成人咱精品视频免费网站 | 4hu影院永久在线播放 | 中文字幕免费在线 | 99久久精品免费观看区一 | 免费网站看v片在线成人国产系列 | 一级毛片免费在线观看网站 | 国产精品青草久久久久婷婷 | 天天干影院 | 国内精品久久久久影院亚洲 | 久久影院在线观看 | 久久综合婷婷 | 夜夜操夜夜 | 97免费视频观看 | 亚洲免费三区 |