概要
在一个数组中选出和最大的互不相邻的子序列，输出其和。
动态规划
作为入门级的动态规划问题，本题实现是非常简单的。本问题与0/1背包问题十分相似，最重要的是想明白动态规划的基本原理。
本题须按照动态规划的思路划分子问题。分治、贪心和动态规划各有不同的角度看待一个问题的子问题，就本题来说，从动态规划的角度出发，对于某一个位置为i的数，只有“选择”和“不选择”两种选择，我们须取这两种选择中和比较大的那个，那么定义长度为i的数组arr的所求最大和为F[i]，则有
F[i] = max(arr[i] + F[i - 2], F[i - 1])
其中，max函数的第一个参数表示选择位置为i的数所得结果，第二个参数表示不选择，通过这样的方式将原问题划分为了两个子问题。
显然，并不需要递归来实现这个式子，最终仅需要一次遍历，在常数的空间复杂度内即可求得结果F[n]。
附录
My SolutionprevMax代表F[i - 1]， pprevMax代表F[i - 2]，这两个值并不需要全部保留，每轮进行更新即可。