题解 | #不相邻最大子序列和#

Python2 解题

令 dp[i]=[a ,b]
a 表示是否使用第i个数字
b 表示前i个数组成的序列的最大和

动态规划的每一步需要分类讨论
如果dp[i-1]没有使用第i-1个数字（dp[i-1][0]==False），则看 dp[i-1], dp[i-1]+array[i], array[i] 哪个大
如果dp[i-1]使用了第i-1个数字（dp[i-1][0]==True），则看 dp[i-1], dp[i-2]+array[i], array[i] 哪个大

因为我们关心最大子序列的和，而dp[i] >= dp[i-1]，因此其实不需要dp数组，我们只需要关注dp[i-2],dp[i-1]即可得到dp[i]，即前i个数组形成的不相邻最大子序列和

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 计算
# @param n int整型 数组的长度
# @param array int整型一维数组 长度为n的数组
# @return long长整型
#
# dp[i] = [a ,b] b表示前i个数组成的序列的最大和, a表示是否使用第i个数字
# dp[i] = if dp[i-1][0]: max(dp[i-1], dp[i-2]+array[i], array[i])
#         else: max(dp[i-1], dp[i-1]+array[i], array[i])

class Solution:
    def subsequence(self , n , array ):
        # write code here
        if n <= 2:
            return max(array)

        dp1 = [True, array[0]]
        dp2_isused = False if array[0] >= array[1] else True
        dp2_sum = max(array[0], array[1])
        dp2 = [dp2_isused, dp2_sum]

        for i in range(2, len(array)):
            tmp_dp = []
            if dp2[0]:
                if dp2[1] >= dp1[1]+array[i] and dp2[1] >= array[i]:
                    tmp_dp = [False, dp2[1]]
                else:
                    tmp_dp = [True, max(dp2[1], dp1[1]+array[i], array[i])]
            else:
                if array[i] > 0:
                    tmp_dp = [True, max(dp2[1] + array[i], array[i])]
                else:
                    tmp_dp = [False, max(dp2[1], dp2[1] + array[i], array[i])]

            dp1 = dp2
            dp2 = tmp_dp

        return dp2[1]