数组中选取非相邻元素以最大化序列和的求解问题

嘿，这个问题其实是经典的「打家劫舍」问题变种——不仅要算出最大和，还得找出对应的元素序列。咱们一步一步来拆解它～

核心思路 #

对于数组里的每个元素，我们只有两个选择：选它或者不选它，基于这两个选择可以推导出状态转移的逻辑：

• 如果选当前元素，那前一个元素绝对不能选，此时的最大和 = 当前元素值 + 前前个位置的最大和（也就是不选前一个元素时的最大和）
• 如果不选当前元素，此时的最大和 = 前一个位置的最大和（不管前一个元素选没选，取最大的那个值）

我们需要维护两个状态数组（或者用变量优化空间）来记录这两种选择的最大和，最后再通过回溯找出具体选中的元素。

示例分析（输入：{4,1,3,4}） #

咱们拿题目给的示例走一遍流程：

1. 初始状态推进：
   • 第1个元素（4，索引0）：选它的和为4，不选则为0，当前最大和是4，记录选中4
   • 第2个元素（1，索引1）：选它的和为1+0=1，不选则为4，显然不选它更优，保持最大和4
   • 第3个元素（3，索引2）：选它的和为3+4=7，不选则为4，此时最大和更新为7，选中3
   • 第4个元素（4，索引3）：选它的和为4+4（前前个位置的不选状态值）=8，不选则为7，所以最大和更新为8，选中这个4
2. 回溯找序列：
   从最后一个元素（索引3的4）倒推：
   • 选它的和（8）大于不选的和（7），把4加入结果，跳两步到索引1
   • 索引1的元素（1）：不选它的和（4）大于选它的和（1），跳一步到索引0
   • 索引0的元素（4）：选它的和（4）大于不选的和（0），把4加入结果
   • 最后反转结果，得到正序的[4,4]，就是咱们要的输出

代码实现（Python） #

下面是完整的代码，包含了计算最大和以及回溯找序列的逻辑：

def find_max_non_adjacent_sequence(arr):
    n = len(arr)
    if n == 0:
        return []
    if n == 1:
        return [arr[0]]
    
    # dp_select[i]：选第i个元素时的最大和
    # dp_not_select[i]：不选第i个元素时的最大和
    dp_select = [0] * n
    dp_not_select = [0] * n
    
    dp_select[0] = arr[0]
    dp_not_select[0] = 0
    
    for i in range(1, n):
        # 选当前元素，只能加前一个不选的和
        dp_select[i] = arr[i] + dp_not_select[i-1]
        # 不选当前元素，取前一个选或不选的最大值
        dp_not_select[i] = max(dp_select[i-1], dp_not_select[i-1])
    
    # 回溯构建序列
    result = []
    i = n - 1
    while i >= 0:
        if i == 0:
            result.append(arr[i])
            break
        # 如果选当前元素的和更大，说明选了它
        if dp_select[i] > dp_not_select[i]:
            result.append(arr[i])
            i -= 2  # 跳两步，因为前一个不能选
        else:
            i -= 1  # 没选当前元素，跳一步看前一个
    
    # 反转得到正序序列
    return result[::-1]

# 测试示例输入
test_arr = [4, 1, 3, 4]
print(find_max_non_adjacent_sequence(test_arr))  # 输出: [4, 4]

优化小提示 #

如果数组很大，我们可以不用维护两个完整的数组，只需要用两个变量prev_select和prev_not_select来记录前一个位置的状态，这样空间复杂度可以从O(n)降到O(1)——感兴趣的话可以自己试试修改代码哦～

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