数组选取元素时排除值为相邻整数的元素的最大和求解方法咨询

问题说明 #

给定整数数组，计算选取元素的最大总和，规则是：选了元素a[i]，就不能选所有值为a[i]-1和a[i]+1的元素。示例：

• 数组a=[1,1,1,1,1,2,2]，输出为5；
• 数组a=[3,3,3,4,4,8,1]，输出为18。

正确解法：统计+动态规划 #

你之前用DP没成功，大概率是直接对着原数组做DP了——这思路不对，因为相同数值的元素是可以全部选的，不需要像打家劫舍那样跳过数组里的相邻元素，真正要规避的是数值相邻的元素组。正确步骤如下：

步骤1：统计每个数值的总权重 #

先遍历数组，统计每个数值对应的元素总和（比如数值1出现5次，总权重就是1*5=5；数值2出现2次，总权重是2*2=4）。可以用哈希表（比如Python的dict）来存，键是数值，值是该数值的总权重。

步骤2：整理有序的数值列表 #

把哈希表里的所有数值提取出来，按从小到大排序，得到一个有序的唯一数值序列。比如第二个示例的数值序列是[1,3,4,8]。

步骤3：动态规划计算最大值 #

这一步的逻辑和经典的「打家劫舍」问题完全一致，因为现在我们要解决的是：在有序的数值序列里，不能选相邻数值（比如3和4是相邻数值，不能同时选它们的总权重），求最大总和。

DP定义与转移

• 定义dp[i]为前i+1个数值（也就是序列中前i位）能拿到的最大总和。
• 初始条件：
  • 如果只有1个数值，dp[0]就是该数值的总权重；
  • 如果有2个数值：
    • 若两个数值相邻（比如1和2），dp[1] = max(第一个数值权重, 第二个数值权重)；
    • 若不相邻（比如1和3），dp[1] = 第一个权重 + 第二个权重。
• 状态转移（从第3个数值开始）：
  • 若当前数值和前一个数值相邻（比如当前是4，前一个是3）：
    dp[i] = max(dp[i-1], dp[i-2] + 当前数值的总权重)
    意思是：要么不选当前数值，取前i-1个的最大值；要么选当前数值，加上前i-2个的最大值（跳过前一个相邻数值）。
  • 若当前数值和前一个数值不相邻（比如当前是8，前一个是4）：
    dp[i] = dp[i-1] + 当前数值的总权重
    意思是：可以直接把当前数值的权重加到之前的最大值上，因为没有冲突。

示例验证 #

拿第二个示例a=[3,3,3,4,4,8,1]来说：

1. 统计权重：1→1，3→9，4→8，8→8；
2. 排序后数值序列：[1,3,4,8]；
3. DP计算：
   • dp[0] = 1
   • dp[1] = 1+9=10（1和3不相邻）
   • dp[2] = max(10, 1+8)=10（3和4相邻，选3的9比选4的8更划算）
   • dp[3] = 10+8=18（4和8不相邻，直接加）
     最终结果18，符合示例。

为什么直接用原数组DP会失败？ #

原数组里的相邻元素可能是相同数值（比如[1,1,1]），按打家劫舍的逻辑会跳过相邻元素，但实际上这些相同数值是可以全部选的——因为规则只禁止选数值±1的元素，相同数值完全没问题。所以必须先把相同数值打包成一个总权重，再对数值序列做DP。

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