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

[wang19980531 (豬精男)]

題目如下，
給予一個數字串列（例如 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
推 alan23273850: 不知道可不可以用dp
推 alan23273850: S(i) = max { a(i) + S(i+2), S(i+1) }
→ alan23273850: 而且這題更有趣的是，整個DP表格可以從尾巴算回來，
→ alan23273850: 換言之，你隨時只要記錄 S(i+1) 跟 S(i+2) 兩個格子
→ alan23273850: 所以既省時 O(n) 又省空間 O(1)
→ alan23273850: 然後如果表格是從頭開始算的話，就可以邊輸入數字邊
→ alan23273850: 計算，這樣整個 a[n] 陣列很大的時候就不怕沒空間存
→ alan23273850: 這題是很好的 leetcode-like 考題喔
推 plsmaop: 感覺是maximum subarray的變形
推 plsmaop: 阿我搞錯了，不太像
→ alan23273850: 這題真好玩，不懂可以再問我
→ alan23273850: 你的演算法之所以不是optimal，是因為很多subtree還
→ alan23273850: 是會重複計算，考慮a1+S4與a2+S4，用你原本的tree法
→ alan23273850: 會發現兩個S4分屬不同子樹，要算兩次，但是只要運用
→ alan23273850: DP技巧的話所有S4只會算過一遍。That's all.
→ wang19980531: 懂了
→ wang19980531: 我試著用DP做看看
→ wang19980531: 謝謝 alin 大大  你的分析好詳細