动态规划求数组非相邻最大和：如何存储对应元素并调试代码？

问题情况 #

作为Python动态编程新手，我编写的代码用于获取数组中构成非相邻元素最大和的元素集合，但仅对部分测试用例有效：

• 测试用例A：[7,2,-3,5,-4,8,6,3,1]，预期输出[7,5,8,3]，实际输出[7,6,1]
• 测试用例B：[7,2,5,8,6]，预期输出[7,5,6]（代码输出正确）
• 测试用例C：[-2,3,1,10,3,-7]，预期输出[3,10]（代码输出正确）

原代码 #

def max_sum(nums):
    #Get the size of the array
    size = len(nums)
    list = []
    cache = [[0 for i in range(3)] for j in range(size)]

    if(size == 0):
        return 0

    if (size == 1):
        return nums[0]

    for i in range(0, size):
        if(nums[i] < 0):
            validate = i

    if(size  == validate + 1):
        return []
    #Create array 'cache' to store non-consecutive maximum values 
    #cache = [0]*(size + 1)

    #base case
    cache[0][2] = nums[0]
    #temp = nums[0]
    cache[0][1] = nums[0]

    for i in range(1, size):
        #temp1 = temp
        cache[i][2] = nums[i] #I store the array numbers at index [I][2]
        cache[i][1] = cache[i - 1][0] + nums[I]  #the max sum is store here
        cache[i][0] = max(cache[i - 1][1], cache[i -1][0])   #current sum is store there
    
    maxset = 0
    for i in range(0, size):          #I get the max sum
        if(cache[i][1] > maxset):
            maxset = cache[i][1]

    for i in range(0, size):         #I get the first element here
        if(cache[i][1] == maxset):
            temp = cache[i][2]

    count = 0
    for i in range(0, size): # I check at what index in the nums array the index 'temp' is store
        if(nums[i] != temp):
            count += 1


    if(size - 1 == count):    #iterate through the nums array to apend the non-adjacent elements
        if(count % 2 == 0):
            for i in range(0, size):
                if i % 2 == 0 and i < size:
                    list.append(nums[i])
        else:
            for i in range(0, size):
                if i % 2 != 0 and i < size:
                    list.append(nums[i])

    list[:]= [item for item in list if item >= 0]

    return list


if __name__ == '__main__':
    A = [7,2,-3,5,-4,8,6,3,1]
    B = [7,2,5,8,6]
    C = [-2,3,1,10,3,-7]

原代码核心问题 #

1. 大小写错误：循环中nums[I]应为nums[i]，会导致运行报错
2. 逻辑错误：通过奇偶索引选择元素的方式完全不符合动态编程的最优子结构逻辑，非相邻元素的最优选择不是固定奇偶，而是根据元素值动态判断
3. 负数处理逻辑错误：遍历找最后一个负数后返回空的逻辑不成立，数组中存在负数但同时有正数时，仍需选择最优正数组合
4. 元素集合追踪错误：通过匹配最大和对应的单个元素，再按奇偶选元素的方式，无法正确回溯出构成最大和的元素路径

要追踪构成最大和的非相邻元素集合，需在动态编程过程中维护两种状态：选当前元素和不选当前元素，同时记录每种状态下的最大和及对应的元素列表。

实现代码 #

def max_non_adjacent_subset(nums):
    if not nums:
        return []
    
    n = len(nums)
    if n == 1:
        return [nums[0]] if nums[0] > 0 else []
    
    # 每个元素存储(当前最大和, 对应的元素列表)
    # include[i]: 选第i个元素时的最优状态
    # exclude[i]: 不选第i个元素时的最优状态
    include = [(0, []) for _ in range(n)]
    exclude = [(0, []) for _ in range(n)]
    
    # 初始化第一个元素的状态
    if nums[0] > 0:
        include[0] = (nums[0], [nums[0]])
    else:
        include[0] = (0, [])
    exclude[0] = (0, [])
    
    for i in range(1, n):
        # 选当前元素：只能基于前一个不选的状态，加上当前元素（若和更大）
        prev_exclude_sum, prev_exclude_list = exclude[i-1]
        new_sum = prev_exclude_sum + nums[i]
        new_list = prev_exclude_list + [nums[i]]
        
        if new_sum > prev_exclude_sum:
            include[i] = (new_sum, new_list)
        else:
            # 加当前元素后和变小，等价于不选当前元素
            include[i] = exclude[i-1]
        
        # 不选当前元素：取前一个选或不选的最优状态
        if include[i-1][0] > exclude[i-1][0]:
            exclude[i] = include[i-1]
        else:
            exclude[i] = exclude[i-1]
    
    # 比较最后一个元素选与不选的状态，返回最优列表
    return include[-1][1] if include[-1][0] > exclude[-1][0] else exclude[-1][1]

# 测试验证
if __name__ == '__main__':
    A = [7,2,-3,5,-4,8,6,3,1]
    print(max_non_adjacent_subset(A))  # 输出: [7,5,8,3]
    B = [7,2,5,8,6]
    print(max_non_adjacent_subset(B))  # 输出: [7,5,6]
    C = [-2,3,1,10,3,-7]
    print(max_non_adjacent_subset(C))  # 输出: [3,10]

代码逻辑说明 #

1. 状态定义：用include和exclude数组分别记录选/不选当前元素时的最大和及元素列表
2. 状态转移：
   • 选当前元素：只能继承前一个元素不选的状态，若加上当前元素后和更大，则更新状态；否则保持前一个不选的状态
   • 不选当前元素：直接继承前一个元素选或不选的最优状态
3. 结果输出：最后比较选/不选最后一个元素的最大和，返回对应的元素列表

内容的提问来源于stack exchange，提问作者vmilk-