这是 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
}

 

Logo

汇聚全球AI编程工具,助力开发者即刻编程。

更多推荐