求不相邻的最大子数组和

问题1：给出一个数组，求出其中一个子集，使得子集中每个元素在原数组中两两都不相邻并使子集的和最大。

解法：对任意一个元素ai ，有两种可能： 选ai ,单选了ai 就不能选ai-1 ；不选ai 那么ai-1 可以选也可以不选，主要根据ai-2的情况，因此动态规划是这样设计的。 

ds[i] 表示选i，a0....ai的最大子数组和；

ns[i]表示不选择 i,a0 ....ai 的最大子数组和；

递推关系是：

ds[i]=ns[i-1]+a[i];

ns[i]= max(ds[i-1],ns[i-1]);