創作內容

1 GP

動態規劃 最大子數列問題

作者:小浣熊ʕ•ᴥ•ʔ│2020-10-19 22:48:40│贊助:2│人氣:63
假設一數列 [−2,2,−3,4,−1,2,1,−5,3]

子數列可能是[-2],[2,-3],[-5,3]

要如何知道最大和的子數列呢?

如果選擇從頭到尾一個加一個來做比較
那這樣的時間複雜度為O(n^2)



如果我們是用動態規劃來解決
時間複雜度為O(n)

做法為
當我們判斷值是否加入數列時
拿值前面的最佳解 + 值 和值本身做比較

如果加起來比較大 值就加入子數列
反之 值自身當作由首至此的最佳解

公式
dp[i] = max(n[i],dp[i - 1] + n[i])

===進入例子===

[−2,2,−3,4,−1,2,1,−5,3]

第一個數不拿來做比較 因為它前面沒有值
最佳解即是本身
[-2,x,x,x,x,x,x,x,x]

第二個數 2
2 與 -2 + 2 做比較
2 > 0
加了會變成0 不加則是2
所以選擇不加
[-2,2,x,x,x,x,x,x,x]

第三個數 -3
-3 與 2 + (-3) 做比較
-3 < -1
加了會變成-1 不加則是-3
所以選擇加入
[-2,2,-1,x,x,x,x,x,x]

第四個數 4
4 與 (-1) + 4 做比較
4 > 3
加了會變成3 不加則是4
所以選擇不加
[-2,2,-1,4,x,x,x,x,x]
.
.
.
.
以此類推 判斷加入與否
最後得到  [-2,2,-1,4,3,5,6,1,4]
子數列最大和為 6 ([4,−1,2,1])


reference: https://www.itread01.com/content/1541564489.html
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4953881
All rights reserved. 版權所有,保留一切權利

相關創作

留言共 3 篇留言

九零年代滑鼠
你是不是可以當老師了

10-20 00:08

小浣熊ʕ•ᴥ•ʔ
老師要很有耐心耶 我做事都三分鐘熱度[e6]10-20 00:55
私は悲しい。
可以幫我規劃嗎

10-20 00:12

小浣熊ʕ•ᴥ•ʔ
每天在holo八卦串回復10幾篇 你很適合去當專欄作家寫文章10-20 00:57
私は悲しい。
專欄作家要很有耐心耶 我寫文章都三分鐘熱度[e6]

10-20 01:32

小浣熊ʕ•ᴥ•ʔ
一天10幾篇持續半年不像阿peko10-20 01:45
我要留言提醒:您尚未登入,請先登入再留言

1喜歡★badfuck 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:動態規劃 背包問題...

追蹤私訊

作品資料夾

yohjstw316民那桑
自製遊戲《幽暗森林裡的糖果屋》釋出宣傳影片 揭露隱藏在甜美糖衣背後的真實黑暗面!看更多我要大聲說昨天19:42


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】