如何用多项式时间求解满足元素最小间距约束的最大权值和子集

该问题存在严格的多项式时间有效求解方法，整体算法时间复杂度为O(n log n)，可轻松支持万级甚至更大规模的数组输入，不存在NP难类的计算障碍。

预处理步骤 #

由于位置差约束仅和元素的相对坐标有关，首先将所有元素按位置x_i做升序排序，得到有序序列(x'_1, p'_1), (x'_2, p'_2), ..., (x'_n, p'_n)，满足x'_1 < x'_2 < ... < x'_n。这一步排序的时间复杂度为O(n log n)。

动态规划递推逻辑 #

定义状态dp[i]为考虑排序后前i个元素时，满足位置差约束的子集能获得的最大权值总和，设置边界值dp[0] = 0，对应空集的权值和为0，匹配题目中允许选取空集的要求。
对排序后的第i个元素，有两种可选决策，取两者的最大值作为dp[i]的最终值：

• 不选取第i个元素：此时能获得的最优权值完全等同于前i-1个元素的最优解，即取值为dp[i-1]
• 选取第i个元素：根据约束要求，选入该元素后，不能同时选取所有和它位置差绝对值≤k的元素。利用排序后x'序列严格递增的特性，通过二分查找定位最大的下标j，满足x'_i - x'_j > k——即所有下标≤j的元素，都和第i个元素满足位置差要求，可以被自由选入。此时选入第i个元素后的最优权值为dp[j] + p'_i，也就是前j个元素的最优解加上第i个元素的权值。

这套状态设计天然兼容权值为负的场景：如果选入某个元素会拉低总权值，递推过程会自然选择不选该元素的分支，最终结果会自动规避无意义的负权选择，和题目允许选取空集的要求完全适配。

整个流程的核心开销来自两部分：一是全量元素排序的O(n log n)时间，二是对n个元素逐一执行二分查找定位兼容下标j的O(n log n)总时间，整体为多项式级时间复杂度，远优于暴力枚举所有子集的指数级解法。

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