作者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/cn.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