Hard

题目描述

给你两个长度为 n 的下标从 0 开始的整数数组 nums1 和 nums2。

你可以选择两个整数 left 和 right，其中 0 <= left <= right < n，接着 交换 两个子数组 nums1[left...right] 和 nums2[left...right]。

  • 例如，设 nums1 = [1,2,3,4,5] 和 nums2 = [11,12,13,14,15]，你选择 left = 1 和 right = 2，那么 nums1 会变为 [1,12,13,4,5] 而 nums2 会变为 [11,2,3,14,15]。

你可以选择执行上述操作 一次 或不执行任何操作。

数组的 分数 取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素的和。

返回 可能的最大分数。

子数组 是数组中连续的一个元素序列。arr[left...right] 表示子数组包含 nums 中下标 left 和 right 之间的元素（含 left 和 right）。

示例 1：

输入：nums1 = [60,60,60], nums2 = [10,90,10]
输出：210
解释：选择 left = 1, right = 1，得到 nums1 = [60,90,60] 和 nums2 = [10,60,10]。
分数为 max(sum(nums1), sum(nums2)) = max(210, 80) = 210。

示例 2：

输入：nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
输出：220
解释：选择 left = 3, right = 4，得到 nums1 = [20,40,20,40,20] 和 nums2 = [50,20,50,70,30]。
分数为 max(sum(nums1), sum(nums2)) = max(140, 220) = 220。

示例 3：

输入：nums1 = [7,11,13], nums2 = [1,1,1]
输出：31
解释：选择不交换任何子数组。
分数为 max(sum(nums1), sum(nums2)) = max(31, 3) = 31。

提示：

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^4

解题思路

这道题要求通过交换两个数组的一个连续子数组来最大化分数。我们需要考虑两种情况：

  1. 从 nums1 开始，用 nums2 的某个子数组替换 nums1 的对应部分
  2. 从 nums2 开始，用 nums1 的某个子数组替换 nums2 的对应部分

核心思想是使用动态规划。对于第一种情况，我们计算差值数组 diff[i] = nums2[i] - nums1[i]，然后找到最大子数组和（Kadane算法）。这个最大值就是我们能通过交换获得的最大增益。

具体来说：

  • 如果我们把 nums1 的子数组 [left, right] 替换为 nums2 的对应部分，总和变化量为 sum(nums2[left:right+1]) - sum(nums1[left:right+1])
  • 这等价于在差值数组中找最大子数组和

同样地，对于第二种情况，我们计算 diff[i] = nums1[i] - nums2[i] 并找最大子数组和。

最终答案是原始两个数组和的最大值，加上通过交换能获得的最大增益。

推荐解法： 使用 Kadane 算法分别计算两种交换情况下的最大增益，时间复杂度 O(n)，空间复杂度 O(1)。

代码实现

class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int sum1 = 0, sum2 = 0;
        
        for (int i = 0; i < n; i++) {
            sum1 += nums1[i];
            sum2 += nums2[i];
        }
        
        // Case 1: Start with nums1, replace subarray with nums2
        int maxGain1 = 0, currentGain1 = 0;
        for (int i = 0; i < n; i++) {
            currentGain1 = max(0, currentGain1 + nums2[i] - nums1[i]);
            maxGain1 = max(maxGain1, currentGain1);
        }
        
        // Case 2: Start with nums2, replace subarray with nums1
        int maxGain2 = 0, currentGain2 = 0;
        for (int i = 0; i < n; i++) {
            currentGain2 = max(0, currentGain2 + nums1[i] - nums2[i]);
            maxGain2 = max(maxGain2, currentGain2);
        }
        
        return max(sum1 + maxGain1, sum2 + maxGain2);
    }
};

class Solution:
    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        sum1, sum2 = sum(nums1), sum(nums2)
        
        # Case 1: Start with nums1, replace subarray with nums2
        max_gain1 = current_gain1 = 0
        for i in range(n):
            current_gain1 = max(0, current_gain1 + nums2[i] - nums1[i])
            max_gain1 = max(max_gain1, current_gain1)
        
        # Case 2: Start with nums2, replace subarray with nums1
        max_gain2 = current_gain2 = 0
        for i in range(n):
            current_gain2 = max(0, current_gain2 + nums1[i] - nums2[i])
            max_gain2 = max(max_gain2, current_gain2)
        
        return max(sum1 + max_gain1, sum2 + max_gain2)

public class Solution {
    public int MaximumsSplicedArray(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        int sum1 = nums1.Sum();
        int sum2 = nums2.Sum();
        
        // Case 1: Start with nums1, replace subarray with nums2
        int maxGain1 = 0, currentGain1 = 0;
        for (int i = 0; i < n; i++) {
            currentGain1 = Math.Max(0, currentGain1 + nums2[i] - nums1[i]);
            maxGain1 = Math.Max(maxGain1, currentGain1);
        }
        
        // Case 2: Start with nums2, replace subarray with nums1
        int maxGain2 = 0, currentGain2 = 0;
        for (int i = 0; i < n; i++) {
            currentGain2 = Math.Max(0, currentGain2 + nums1[i] - nums2[i]);
            maxGain2 = Math.Max(maxGain2, currentGain2);
        }
        
        return Math.Max(sum1 + maxGain1, sum2 + maxGain2);
    }
}

var maximumsSplicedArray = function(nums1, nums2) {
    const n = nums1.length;
    const sum1 = nums1.reduce((a, b) => a + b, 0);
    const sum2 = nums2.reduce((a, b) => a + b, 0);
    
    // Case 1: Start with nums1, replace subarray with nums2
    let maxGain1 = 0, currentGain1 = 0;
    for (let i = 0; i < n; i++) {
        currentGain1 = Math.max(0, currentGain1 + nums2[i] - nums1[i]);
        maxGain1 = Math.max(maxGain1, currentGain1);
    }
    
    // Case 2: Start with nums2, replace subarray with nums1
    let maxGain2 = 0, currentGain2 = 0;
    for (let i = 0; i < n; i++) {
        currentGain2 = Math.max(0, currentGain2 + nums1[i] - nums2[i]);
        maxGain2 = Math.max(maxGain2, currentGain2);
    }
    
    return Math.max(sum1 + maxGain1, sum2 + maxGain2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

相关题目