拼接数组的最大分数

标签: 数组 动态规划

难度: Hard

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

你可以选择两个整数 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 <= 105
  • 1 <= nums1[i], nums2[i] <= 104

Submission

运行时间: 71 ms

内存: 30.8 MB

class Solution:
    # def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
    #     n = len(nums1)
    #     max_result = 0
    #     for i in range(n):
    #         for j in range(i, n):
    #             tmp = nums1[i: j + 1]
    #             tmp2 = nums2[i: j + 1]
    #             sum1 = sum(nums1) - sum(tmp) + sum(tmp2)
    #             sum2 = sum(nums2) + sum(tmp) - sum(tmp2)
    #             max_tmp = max(sum1, sum2)
    #             if max_result < max_tmp:
    #                 max_result = max_tmp

    #     return max_result
    def solve(self, nums1: List[int], nums2: List[int]) -> int:
        maxSum = s = 0
        # 求最大子数组的和
        for x, y in zip(nums1, nums2):
            s += y - x
            if s < 0: s = 0
            if s > maxSum: maxSum = s
        return sum(nums1) + maxSum

    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))

Explain

本题解使用了贪心算法与Kadane算法（最大子数组和）的思想。首先，可以观察到交换子数组后，nums1与nums2的总和不变，变化的只是两者的分配。因此，问题转化为找到一段区间（子数组），使得在交换后，两个数组中的最大总和最大。对于任何一对位置i，交换nums1[i]与nums2[i]得到的增益是(nums2[i] - nums1[i])。我们要找的是一个子数组，使得这个增益最大化。这可以通过Kadane算法实现，即计算最大子数组和，然后将这个最大增益加到原始数组nums1的总和上。为了确保考虑了所有可能，还需要从nums2的角度做同样的计算，即将nums1与nums2的角色互换，再次计算最大增益并加到nums2的总和上。最后，比较这两种情况的结果，取最大值。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def solve(self, nums1: List[int], nums2: List[int]) -> int:
        maxSum = s = 0 # 初始化最大子数组和maxSum和当前子数组和s
        # 遍历nums1和nums2的元素
        for x, y in zip(nums1, nums2):
            s += y - x # 更新当前子数组和
            if s < 0: s = 0 # 如果当前子数组和小于0，重置为0
            if s > maxSum: maxSum = s # 更新最大子数组和
        return sum(nums1) + maxSum # 返回修改后的nums1总和增加最大子数组和

    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
        # 计算两种可能的最大分数，并返回最大值
        return max(self.solve(nums1, nums2), self.solve(nums2, nums1))

Explore

在计算增益时使用(nums2[i] - nums1[i])是为了确定交换nums1[i]和nums2[i]后的分数变化量。增益的计算反映了交换这两个元素后nums1数组的总和增加了多少。如果nums2[i]大于nums1[i]，那么交换后nums1的总和会增加(nums2[i] - nums1[i])，这是因为我们把一个较大的数nums2[i]加到了nums1中，同时移除了一个较小的数nums1[i]。因此，这种计算方式可以直接评估每一次交换带来的净收益，帮助我们决定是否进行此交换以达到最大化nums1的总和。

Kadane算法适用于本问题是因为我们需要找到一个子数组（即连续元素的集合），使得其对总和的正向贡献最大化。在本题中，每个元素的增益是(nums2[i] - nums1[i])，我们要找的是这些增益值组成的子数组，它们的总和最大。Kadane算法恰好用于快速找出一个数组中的最大子数组和，这使得它成为计算由增益构成的数组的最大子数组和的理想选择。通过这种方式，我们可以有效地找到最优的交换策略，即在哪个连续子区间进行交换可以最大化改进数组的总和。

在Kadane算法中，如果当前子数组和小于0，将其重置为0是因为负的子数组和对寻找最大子数组总和没有帮助，反而会减少总和。当我们遇到这种情况时，意味着从当前位置开始重新计算子数组和可能得到一个更大的值。这是因为任何包含负总和的前缀都不能是最优的子数组的一部分，所以重置子数组和可以帮助我们摆脱之前的负积累，从当前点重新开始计算，可能找到一个新的、更大的子数组和。

从nums1和nums2两个角度分别计算可以保证找到全局最优解，因为这种方法考虑了所有可能的交换方案。通过分别以nums1和nums2作为基准数组并计算最大增益，我们可以确保不遗漏任何一个可能导致总和增加的交换方案。然后通过比较这两种情况的结果，我们可以选择两者中的最大值，这确保了无论最佳交换策略属于哪一个数组，都能被正确考虑并实现最大化总和的目标。