Microsoft OA 相邻交换：每个元素最多一次时最大化位置加权和

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 数组元素可为任意整数，位置权重从 1 开始。
• 交换是可选操作；每个原始元素最多参与一次，所以选出的相邻下标对不能共享端点。
• 不把交换后的元素再次拿去交换；若面试官允许多步搬移，此 DP 不适用。

解题路线

1. 先算原序列基准分。交换原位置 i 与 i+1 的分数变化为 a[i]−a[i+1]：两项相减即可消去其他位置。
2. 把每条相邻边的增益看成边权。合法交换集合是不相交边集合，即路径图最大权匹配；负增益边可不选。
3. 令 dp[j] 是前 j 个元素可获得的最大额外分：不交换末元素为 dp[j−1]，交换末两个为 dp[j−2]+a[j−2]−a[j−1]。取较大者。
4. 只保留前两个 DP 值即可；若还要输出交换位置，保存选择标记并从右向左回溯。

手动走一遍

[2,1,4,3] 的原分为 2+2+12+12=28。交换 (2,1) 增益 1，交换 (4,3) 也增益 1，边不相邻，答案 30。若只有 [1,2]，唯一交换增益 −1，应选择不交换。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections.abc import Sequence


def max_weighted_sum(values: Sequence[int]) -> int:
    """Each original element may be used in at most one adjacent swap."""
    base = sum((i + 1) * value for i, value in enumerate(values))
    prev_two = prev_one = 0
    for i in range(1, len(values)):
        gain = values[i - 1] - values[i]
        prev_two, prev_one = prev_one, max(prev_one, prev_two + gain)
    return base + prev_one


if __name__ == "__main__":
    assert max_weighted_sum([2, 1, 4, 3]) == 30

复杂度

基准分和 DP 各扫一遍，O(n) 时间、O(1) 额外空间。若需恢复所选交换对，存 O(n) 个决策。

易错点与追问

容易失分的边界

• 把问题当成任意次数冒泡排序；那会让某元素参与多次交换，违背题目约束。
• 只取每条正增益边，可能同时选择共享元素的两条边。
• 在 Python 中误写成同时更新但把 dp[j−2] 与 dp[j−1] 的旧值混淆。
• 空数组、单元素以及所有交换增益均为负时，答案就是原始分。

继续深挖

• 若必须恰好做 k 次交换，增加交换次数维度，时间 O(nk)。
• 若每个元素最多移动两次，路径匹配模型为何失效？
• 如需返回字典序最小的最优交换集合，平局时如何回溯？