数组中非相邻数最大和

给定一个数组，相邻的的数不能同时选，求从该数组中选出若干数，使它们的和最大。

分析：

    一看到求和最大，意味着求一个最优解。方法不外乎递归+回溯、动态规划。

   考虑到数组很容易从其一个较小的规模出发去分析解题思路。子问题与原问题形式一样，记住已经解决过的子问题的解，由子问题的解推导出原问题的解。很明显该题同时符合动态规划的两大特征：最优子结构、重叠子问题。

    只要满足最优子结构性质就可以使用动态规划，如果还具有子问题重叠，则更能彰显动态规划的优势。

   以dp[i]记录截止到第i个元素为止，所能求得的符合约束条件的最大和。该位置处的值的来源有两个dp[i-2]+alist[i]和dp[i-1]，很明显我们需要取最大的一个。

    初始dp[0]=0元素值，dp[1]=max(1元素值，dp[0])

    若要找出选中了哪些元素，一般采用回溯法。

python代码如下

def nonadjacentnum_maxsum(alist):

    length=len(alist)

    dp=[0]*length

    dp[0]=alist[0]

    for i in range(1,length):

        if i==1:

            dp[i]=max(dp[0],alist[1])

        else:

            dp[i]=max(dp[i-2]+alist[i],dp[i-1])

    #回溯

    selnum=[]

    i=length-1

    ele=dp[length-1]        #初始

    while i>=0 :

        if i==0:

            selnum=[alist[0]]+selnum

            break

        if dp[i-1]==ele:            #找到相邻两个元素不同时，右边的dp[i]，它对应的alist[i]就是选中的元素

            i-=1

        else:

            ele=dp[i]

            selnum=[alist[i]]+selnum

            i-=2           #跳过一个元素

    return dp,selnum

测试用例

>>> nonadjacentnum_maxsum([2])

([2], [2])

>>> nonadjacentnum_maxsum([2,4,7,0,10,1])

([2, 4, 9, 9, 19, 19], [2, 7, 10])

>>> nonadjacentnum_maxsum([2,1,4])

([2, 2, 6], [2, 4])

>>> nonadjacentnum_maxsum([2,1])

([2, 2], [2])

>>>