2026-02-23：交换元素后的最大交替和。用go语言，给定一个整数数组 nums，定义其交替和为下标偶数位置元素之和减去奇数位置元素之和（即 nums[0] - nums[1] + nums[2] - …）。

另有一组下标对 swaps，其中每个 [p, q] 表示你可以任意次交换位置 p 和 q 上的元素。因为交换可以重复进行，这意味着在由这些交换边构成的图的每个连通分量内，数组元素可以任意重排到这些位置上。

在允许按 swaps 规则进行任意交换的情况下，问能够得到的最大交替和是多少？请返回该最大值。

2 <= nums.length <= 100000。

1 <= nums[i] <= 1000000000。

0 <= swaps.length <= 100000。

swaps[i] = [pi, qi]。

0 <= pi < qi <= nums.length - 1。

[pi, qi] != [pj, qj]。

输入：nums = [1,2,3], swaps = [[0,2],[1,2]]。

输出：4。

解释：

当 nums 为 [2, 1, 3] 或 [3, 1, 2] 时，可以实现最大交替和。例如，你可以通过以下方式得到 nums = [2, 1, 3]。

交换 nums[0] 和 nums[2]。此时 nums 为 [3, 2, 1]。

交换 nums[1] 和 nums[2]。此时 nums 为 [3, 1, 2]。

交换 nums[0] 和 nums[2]。此时 nums 为 [2, 1, 3]。

题目来自力扣3695。

解题思路

这是一个基于并查集和贪心策略的问题。

1. 理解交换规则

• 给定一组下标对 [p, q]，可以任意次交换位置 p 和 q 的元素
• 这种交换关系会形成图的连通分量，在每个连通分量内，元素可以任意排列
• 也就是说，我们可以将每个连通分量内的元素重新分配到该分量中的任意位置上

2. 交替和的定义

• 交替和 = 偶数下标元素之和 - 奇数下标元素之和
• 偶数下标位置在计算中取正号，奇数下标位置取负号

3. 贪心策略

为了使交替和最大：

• 尽量把大的数放在偶数下标（取正号的位置）
• 尽量把小的数放在奇数下标（取负号的位置）

4. 解题步骤

第一步：构建连通关系

• 使用并查集将所有可以交换的位置合并到同一个集合中
• 每个集合代表一个可以自由排列元素的连通分量

第二步：统计每个分量的奇数位置数量

• 在每个连通分量中，需要知道该分量包含多少个奇数下标
• 这些奇数位置在最终排列中应该放最小的几个数（因为取负号）

第三步：分组排序

• 将原始数组中的元素按照它们所属的连通分量分组
• 对每组内的元素进行升序排序

第四步：分配元素

• 对于每个连通分量：
  • 设该分量有 k 个奇数位置
  • 将排序后的数组中最小的 k 个数分配到奇数位置（取负号）
  • 将剩余的数分配到偶数位置（取正号）
  • 这样能最大化该分量的贡献

第五步：计算结果

• 将所有分量的贡献相加得到最终的最大交替和

算法复杂度

时间复杂度：O(n log n)

• 并查集操作近似 O(n)
• 对每个分组的排序，总体排序复杂度 O(n log n)
• 遍历数组求和 O(n)

额外空间复杂度：O(n)

• 并查集数组 O(n)
• 分组存储数组 O(n)

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
)

type unionFind struct {
	fa  []int // 代表元
	odd []int // 集合中的奇数个数
}

func newUnionFind(n int) unionFind {
	fa := make([]int, n)
	odd := make([]int, n)
	// 一开始有 n 个集合 {0}, {1}, ..., {n-1}
	// 集合 i 的代表元是自己
	for i := range fa {
		fa[i] = i
		odd[i] = i % 2
	}
	return unionFind{fa, odd}
}

// 返回 x 所在集合的代表元
// 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
func (u unionFind) find(x int) int {
	// 如果 fa[x] == x，则表示 x 是代表元
	if u.fa[x] != x {
		u.fa[x] = u.find(u.fa[x]) // fa 改成代表元
	}
	return u.fa[x]
}

// 把 from 所在集合合并到 to 所在集合中
func (u *unionFind) merge(from, to int) {
	x, y := u.find(from), u.find(to)
	if x == y { // from 和 to 在同一个集合，不做合并
		return
	}
	u.fa[x] = y          // 合并集合
	u.odd[y] += u.odd[x] // 更新集合中的奇数个数
}

func maxAlternatingSum(nums []int, swaps [][]int) (ans int64) {
	n := len(nums)
	uf := newUnionFind(n)
	for _, p := range swaps {
		uf.merge(p[0], p[1])
	}

	g := make([][]int, n)
	for i, x := range nums {
		f := uf.find(i)
		g[f] = append(g[f], x) // 相同集合的元素分到同一组
	}

	for i, a := range g {
		if a == nil {
			continue
		}
		slices.Sort(a)
		odd := uf.odd[i]
		// 小的取负号，大的取正号
		for j, x := range a {
			if j < odd {
				ans -= int64(x)
			} else {
				ans += int64(x)
			}
		}
	}
	return
}

func main() {
	nums := []int{1, 2, 3}
	swaps := [][]int{{0, 2}, {1, 2}}
	result := maxAlternatingSum(nums, swaps)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

class UnionFind:
    def __init__(self, n: int):
        # 代表元
        self.fa = list(range(n))
        # 集合中的奇数个数
        self.odd = [i % 2 for i in range(n)]
    
    def find(self, x: int) -> int:
        """返回 x 所在集合的代表元，同时做路径压缩"""
        if self.fa[x] != x:
            self.fa[x] = self.find(self.fa[x])
        return self.fa[x]
    
    def merge(self, from_node: int, to: int) -> None:
        """把 from_node 所在集合合并到 to 所在集合中"""
        x, y = self.find(from_node), self.find(to)
        if x == y:  # 已经在同一个集合，不做合并
            return
        self.fa[x] = y  # 合并集合
        self.odd[y] += self.odd[x]  # 更新集合中的奇数个数

class Solution:
    def maxAlternatingSum(self, nums: List[int], swaps: List[List[int]]) -> int:
        n = len(nums)
        uf = UnionFind(n)
        
        # 合并可以交换的位置
        for p in swaps:
            uf.merge(p[0], p[1])
        
        # 将相同集合的元素分到同一组
        groups = [[] for _ in range(n)]
        for i, x in enumerate(nums):
            f = uf.find(i)
            groups[f].append(x)
        
        ans = 0
        for i, group in enumerate(groups):
            if not group:  # 跳过空组
                continue
            group.sort()
            odd_count = uf.odd[i]
            # 小的取负号，大的取正号
            for j, x in enumerate(group):
                if j < odd_count:
                    ans -= x
                else:
                    ans += x
        
        return ans

def main():
    nums = [1, 2, 3]
    swaps = [[0, 2], [1, 2]]
    solution = Solution()
    result = solution.maxAlternatingSum(nums, swaps)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;

class UnionFind {
public:
    vector<int> fa;   // 代表元
    vector<int> odd;  // 集合中的奇数个数

    UnionFind(int n) {
        fa.resize(n);
        odd.resize(n);
        // 一开始有 n 个集合 {0}, {1}, ..., {n-1}
        // 集合 i 的代表元是自己
        for (int i = 0; i < n; i++) {
            fa[i] = i;
            odd[i] = i % 2;
        }
    }

    // 返回 x 所在集合的代表元
    // 同时做路径压缩，也就是把 x 所在集合中的所有元素的 fa 都改成代表元
    int find(int x) {
        // 如果 fa[x] == x，则表示 x 是代表元
        if (fa[x] != x) {
            fa[x] = find(fa[x]); // fa 改成代表元
        }
        return fa[x];
    }

    // 把 from 所在集合合并到 to 所在集合中
    void merge(int from, int to) {
        int x = find(from), y = find(to);
        if (x == y) { // from 和 to 在同一个集合，不做合并
            return;
        }
        fa[x] = y;          // 合并集合
        odd[y] += odd[x];   // 更新集合中的奇数个数
    }
};

class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums, vector<vector<int>>& swaps) {
        int n = nums.size();
        UnionFind uf(n);

        // 合并可以交换的位置
        for (const auto& p : swaps) {
            uf.merge(p[0], p[1]);
        }

        // 将相同集合的元素分到同一组
        vector<vector<int>> groups(n);
        for (int i = 0; i < n; i++) {
            int f = uf.find(i);
            groups[f].push_back(nums[i]);
        }

        long long ans = 0;
        for (int i = 0; i < n; i++) {
            if (groups[i].empty()) {
                continue;
            }
            sort(groups[i].begin(), groups[i].end());
            int odd_count = uf.odd[i];
            // 小的取负号，大的取正号
            for (int j = 0; j < groups[i].size(); j++) {
                if (j < odd_count) {
                    ans -= groups[i][j];
                } else {
                    ans += groups[i][j];
                }
            }
        }

        return ans;
    }
};

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> swaps = {{0, 2}, {1, 2}};
    Solution solution;
    long long result = solution.maxAlternatingSum(nums, swaps);
    cout << result << endl;
    return 0;
}