如何打印数组中不相邻元素构成的最大和子序列？附最大和计算代码

嘿，很高兴能帮你搞定这个问题！你已经有了计算不相邻元素最大和的核心逻辑，现在只需要给它加个「记忆」功能，就能追踪到构成最大和的具体元素啦。咱们一步步来：

你的原代码用incl（包含当前元素的最大和）和excl（不包含当前元素的最大和）两个变量实现了O(n)时间复杂度的计算，但这两个变量只记录了数值，没存对应的元素序列。我们只需要把它们升级成同时存储和值与元素列表的元组，就能在计算过程中同步追踪元素。

修改后的完整代码 #

def find_max_sum_with_elements(arr):
    # 初始化：incl = (包含前一个元素的最大和, 对应元素列表)
    # excl = (不包含前一个元素的最大和, 对应元素列表)
    incl = (0, [])
    excl = (0, [])
    
    for num in arr:
        # 先确定新的excl：取之前incl和excl中较大的那个（同步取对应列表）
        new_excl = excl if excl[0] > incl[0] else incl
        
        # 更新incl：用之前的excl的和加上当前元素，列表也追加当前元素
        new_incl_sum = excl[0] + num
        new_incl_list = excl[1] + [num]
        incl = (new_incl_sum, new_incl_list)
        
        excl = new_excl
    
    # 最后返回和更大的那个结果（和相同则返回先出现的序列）
    max_sum, max_elements = excl if excl[0] > incl[0] else incl
    print(f"最大和为：{max_sum}")
    print(f"构成该和的元素：{max_elements}")
    return max_sum, max_elements

怎么用？ #

举个例子测试一下：

arr = [3, 2, 7, 10]
find_max_sum_with_elements(arr)

输出会是：

最大和为：13
构成该和的元素：[3, 10]

再试一个有负数的情况：

arr = [5, -1, 3, -2, 4]
find_max_sum_with_elements(arr)

输出：

最大和为：9
构成该和的元素：[5,4]

关键细节说明 #

• 时间复杂度还是O(n)，和原代码一样高效，每个元素只处理一次。
• 如果存在多个元素序列的和等于最大值，这个代码会返回最先出现的那个最优序列（因为当和相等时，我们选择了incl的序列，也就是更早的选择）。
• 初始化的(0, [])是为了处理空数组或者全负数的情况（此时最大和是0，对应空列表，当然你也可以根据需求调整这个初始值）。

内容的提问来源于stack exchange，提问作者Charanrajh Pepakayala