题目如下，
给予一个数字串行（例如 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的了
但程式耗时仍然超时
想请问哪一步还能够更加精简

不知道可不可以用dpS(i) = max { a(i) + S(i+2), S(i+1) }而且这题更有趣的是，整个DP表格可以从尾巴算回来，换言之，你随时只要记录 S(i+1) 跟 S(i+2) 两个格子所以既省时 O(n) 又省空间 O(1)然后如果表格是从头开始算的话，就可以边输入数字边计算，这样整个 a[n] 阵列很大的时候就不怕没空间存这题是很好的 leetcode-like 考题喔

感觉是maximum subarray的变形阿我搞错了，不太像

这题真好玩，不懂可以再问我你的算法之所以不是optimal，是因为很多subtree还是会重复计算，考虑a1+S4与a2+S4，用你原本的tree法会发现两个S4分属不同子树，要算两次，但是只要运用DP技巧的话所有S4只会算过一遍。That's all.

懂了我试着用DP做看看谢谢 alin 大大 你的分析好详细