作者wang19980531 (豬精男)
看板Grad-ProbAsk
標題[理工] 演算法 選取最大的數的和
時間Sat May 19 22:38:01 2018
題目如下，
給予一個數字串列（例如 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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1526740683.A.26D.html
1F：推 alan23273850: 不知道可不可以用dp 05/20 01:03
2F：推 alan23273850: S(i) = max { a(i) + S(i+2), S(i+1) } 05/20 01:08
3F：→ alan23273850: 而且這題更有趣的是，整個DP表格可以從尾巴算回來， 05/20 03:40
4F：→ alan23273850: 換言之，你隨時只要記錄 S(i+1) 跟 S(i+2) 兩個格子 05/20 03:41
5F：→ alan23273850: 所以既省時 O(n) 又省空間 O(1) 05/20 03:41
6F：→ alan23273850: 然後如果表格是從頭開始算的話，就可以邊輸入數字邊 05/20 03:42
7F：→ alan23273850: 計算，這樣整個 a[n] 陣列很大的時候就不怕沒空間存 05/20 03:43
8F：→ alan23273850: 這題是很好的 leetcode-like 考題喔 05/20 03:44
9F：推 plsmaop: 感覺是maximum subarray的變形 05/20 06:20
10F：推 plsmaop: 阿我搞錯了，不太像 05/20 06:25
11F：→ alan23273850: 這題真好玩，不懂可以再問我 05/20 12:30
12F：→ alan23273850: 你的演算法之所以不是optimal，是因為很多subtree還 05/20 14:43
13F：→ alan23273850: 是會重複計算，考慮a1+S4與a2+S4，用你原本的tree法 05/20 14:44
14F：→ alan23273850: 會發現兩個S4分屬不同子樹，要算兩次，但是只要運用 05/20 14:44
15F：→ alan23273850: DP技巧的話所有S4只會算過一遍。That's all. 05/20 14:44
16F：→ wang19980531: 懂了 05/20 16:41
17F：→ wang19980531: 我試著用DP做看看 05/20 16:42
18F：→ wang19980531: 謝謝 alin 大大 你的分析好詳細 05/21 09:03