DeepSeek LeetCode 2321.拼接数组的最大分数 Go实现

这是 LeetCode 2321「拼接数组的最大分数」的 Go 语言实现：

```go
func maximumsSplicedArray(nums1 []int, nums2 []int) int {
n := len(nums1)
sum1, sum2 := 0, 0
diff := make([]int, n)

// 计算两个数组的总和及差值数组
for i := 0; i < n; i++ {
sum1 += nums1[i]
sum2 += nums2[i]
diff[i] = nums2[i] - nums1[i]
}

// 情况1：从nums2中选一段替换到nums1
maxGain1 := maxSubarraySum(diff) // 最大子数组和

// 情况2：从nums1中选一段替换到nums2
// 等价于求 diff 的相反数的最大子数组和
maxGain2 := maxSubarraySum(negate(diff))

// 取两种方案的最大值
return max(sum1+maxGain1, sum2+maxGain2)
}

// 最大子数组和（Kadane算法，允许空子数组，最小为0）
func maxSubarraySum(arr []int) int {
curr, best := 0, 0
for _, val := range arr {
curr += val
if curr < 0 {
curr = 0
}
if curr > best {
best = curr
}
}
return best
}

// 返回数组的相反数
func negate(arr []int) []int {
res := make([]int, len(arr))
for i, v := range arr {
res[i] = -v
}
return res
}

func max(a, b int) int {
if a > b {
return a
}
return b
}
```

核心思路：

1. 问题转化：交换一段子数组相当于计算差分数组的最大子段和
· 定义 diff[i] = nums2[i] - nums1[i]
· 将 nums2 的一段替换到 nums1，增益为 sum(diff[l..r])
· 将 nums1 的一段替换到 nums2，相当于 diff 取反后再求最大子段和
2. 算法步骤：
· 计算 sum1、sum2 和 diff 数组
· 用 Kadane 算法求 diff 的最大子段和（允许空子段，最小为0）
· 同理求 -diff 的最大子段和
· 答案 = max(sum1+增益1, sum2+增益2)
3. 复杂度：O(n) 时间，O(n) 额外空间（diff 数组可优化为 O(1) 空间）

package main

func maximumsSplicedArray(nums1 []int, nums2 []int) int {
n := len(nums1)
sum1, sum2 := 0, 0
diff := make([]int, n)
for i := 0; i < n; i++ {
sum1 += nums1[i]
sum2 += nums2[i]
diff[i] = nums2[i] - nums1[i]
}

// 计算最大子段和（允许空子段，即至少为0）
maxGain1 := maxSubarraySum(diff) // 对nums1的增益
maxGain2 := maxSubarraySum(neg(diff)) // 对nums2的增益

ans := sum1 + maxGain1
if sum2+maxGain2 > ans {
ans = sum2 + maxGain2
}
return ans
}

// 计算最大子段和（如果全为负数则返回0）
func maxSubarraySum(arr []int) int {
maxEndingHere := 0
maxSoFar := 0
for _, v := range arr {
maxEndingHere += v
if maxEndingHere < 0 {
maxEndingHere = 0
}
if maxEndingHere > maxSoFar {
maxSoFar = maxEndingHere
}
}
return maxSoFar
}

// 返回数组的相反数
func neg(arr []int) []int {
res := make([]int, len(arr))
for i, v := range arr {
res[i] = -v
}
return res
}