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

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)
}

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

from typing import List

class UnionFind:
    def __init__(self, n: int):
        # 代表元
        self.fa = list(range(n))
        # 集合中的奇数个数
        self.odd = [i % 2for 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()

#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;
    return0;
}