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

另有一组下标对 swaps，其中每个 [p， q] 暗意你不错淘气次交换位置 p 和 q 上的元素。因为交换不错重叠进行，这意味着在由这些交换边组成的图的每个连通重量内，数组元素不错淘气重排到这些位置上。

在允许按 swaps 章程进行淘气交换的情况下，问大概得到的最大瓜代和是几许？请复返该最大值。

2

1

0

swaps[i] = [pi， qi]。

0

[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

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 % 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

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

#include

#include

#include

using namespace std;

class UnionFind {

public:

vector fa; // 代表元

vector odd; // 麇集会的奇数个数

UnionFind(int n) {

fa.resize(n);

odd.resize(n);

// 一驱动有 n 个蚁集 {0}， {1}， ...， {n-1}

// 蚁集 i 的代表元是我方

for (int i = 0; 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& nums， vector>& swaps) {

int n = nums.size;

UnionFind uf(n);

// 合并不错交换的位置

for (const auto& p : swaps) {

uf.merge(p[0]， p[1]);

}

// 将雷同蚁集的元素分到并吞组

vector> groups(n);

for (int i = 0; i

int f = uf.find(i);

groups[f].push_back(nums[i]);

}

long long ans = 0;

for (int i = 0; i

if (groups[i].empty) {

continue;

}

sort(groups[i].begin， groups[i].end);

int odd_count = uf.odd[i];

// 小的取负号，大的取正号

for (int j = 0; j

if (j

ans -= groups[i][j];

} else {

ans += groups[i][j];

}

}

}

return ans;

}

};

int main {

vector nums = {1， 2， 3};

vector> swaps = {{0， 2}， {1， 2}};

Solution solution;

long long result = solution.maxAlternatingSum(nums， swaps);

cout

return0;

}

咱们肯定东说念主工智能为平凡东说念主提供了一种“增强器具”，并起劲于共享全主张的AI常识。在这里，您不错找到最新的AI科普著作、器具评测、提高遣散的秘密以及行业知悉。

接待讲理“福大大架构师逐日一题”，发音尘可取得口试贵府，让AI助力您的改日发展。