[理工] 演算法 選取最大的數的和

看板Grad-ProbAsk作者 (豬精男)時間6年前 (2018/05/19 22:38), 編輯推噓4(4推 0噓 14→)
留言18則, 3人參與, 6年前最新討論串1/1
題目如下， 給予一個數字串列（例如 2 3 1 4 8） 從中任意選取數字，但不能選取相鄰的兩個數 求選取數字的和的最大可能值 例如以上面的數字串列作舉例，最大的和為 2 1 8 或3 8 等於11 看到這樣的題目 我的作法如下： 以2和3作為一棵樹的起始節點， 2的節點的left 指向 1（i+2) right 指向4(i+3) 1的left再指向8 right指向null 此做法可以省去一般窮舉法 多餘的可能 例如（2 8） 我認為我的演算法已經是optimal的了 但程式耗時仍然超時 想請問哪一步還能夠更加精簡 ----- Sent from JPTT on my iPhone -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.33.123 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1526740683.A.26D.html
推
05/20 01:03, 6年前 , 1F
不知道可不可以用dp
05/20 01:03, 1F
推
05/20 01:08, 6年前 , 2F
S(i) = max { a(i) + S(i+2), S(i+1) }
05/20 01:08, 2F
→
05/20 03:40, 6年前 , 3F
而且這題更有趣的是，整個DP表格可以從尾巴算回來，
05/20 03:40, 3F
→
05/20 03:41, 6年前 , 4F
換言之，你隨時只要記錄 S(i+1) 跟 S(i+2) 兩個格子
05/20 03:41, 4F
→
05/20 03:41, 6年前 , 5F
所以既省時 O(n) 又省空間 O(1)
05/20 03:41, 5F
→
05/20 03:42, 6年前 , 6F
然後如果表格是從頭開始算的話，就可以邊輸入數字邊
05/20 03:42, 6F
→
05/20 03:43, 6年前 , 7F
計算，這樣整個 a[n] 陣列很大的時候就不怕沒空間存
05/20 03:43, 7F
→
05/20 03:44, 6年前 , 8F
這題是很好的 leetcode-like 考題喔
05/20 03:44, 8F
推
05/20 06:20, 6年前 , 9F
感覺是maximum subarray的變形
05/20 06:20, 9F
推
05/20 06:25, 6年前 , 10F
阿我搞錯了，不太像
05/20 06:25, 10F
→
05/20 12:30, 6年前 , 11F
這題真好玩，不懂可以再問我
05/20 12:30, 11F
→
05/20 14:43, 6年前 , 12F
你的演算法之所以不是optimal，是因為很多subtree還
05/20 14:43, 12F
→
05/20 14:44, 6年前 , 13F
是會重複計算，考慮a1+S4與a2+S4，用你原本的tree法
05/20 14:44, 13F
→
05/20 14:44, 6年前 , 14F
會發現兩個S4分屬不同子樹，要算兩次，但是只要運用
05/20 14:44, 14F
→
05/20 14:44, 6年前 , 15F
DP技巧的話所有S4只會算過一遍。That's all.
05/20 14:44, 15F
→
05/20 16:41, 6年前 , 16F
懂了
05/20 16:41, 16F
→
05/20 16:42, 6年前 , 17F
我試著用DP做看看
05/20 16:42, 17F
→
05/21 09:03, 6年前 , 18F
謝謝 alin 大大 你的分析好詳細
05/21 09:03, 18F
‣ 更多 wang19980531 的文章
文章代碼(AID): #1R03RB9j (Grad-ProbAsk)