2321-拼接数组的最大分数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

给你两个下标从 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

本题 视频讲解 已出炉，欢迎点赞三连~

设 s_1 = \sum\limits_{i}\textit{nums}_1[i]。

交换 [\textit{left},\textit{right}] 范围内的元素后，对于 nums}’_1 有

\sum\limits_{i}\textit{nums}’_1[i] = s_1 - (\textit{nums}_1[\textit{left}] + \cdots + \textit{nums}_1[\textit{right}]) + (\textit{nums}_2[\textit{left}] + \cdots + \textit{nums}_2[\textit{right}])

合并相同下标，等号右侧变形为

s_1 + (\textit{nums}_2[\textit{left}]-\textit{nums}_1[\textit{left}]) + \cdots + (\textit{nums}_2[\textit{right}]-\textit{nums}_1[\textit{right}])

设 diff}[i] = \textit{nums}_2[i]-\textit{nums}_1[i]，上式变为

s_1 + \textit{diff}[\textit{left}] + \cdots + \textit{diff}[\textit{right}]

为了最大化上式，我们需要最大化 diff 数组的 53. 最大子数组和 （允许子数组为空）。

对于 nums}_2 也同理，求这两者的最大值，即为答案。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    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))
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        return Math.max(solve(nums1, nums2), solve(nums2, nums1));
    }

    int solve(int[] nums1, int[] nums2) {
        int s1 = 0, maxSum = 0;
        for (int i = 0, s = 0; i < nums1.length; ++i) {
            s1 += nums1[i];
            s = Math.max(s + nums2[i] - nums1[i], 0);
            maxSum = Math.max(maxSum, s);
        }
        return s1 + maxSum;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int solve(vector<int> &nums1, vector<int> &nums2) {
        int s1 = 0, maxSum = 0;
        for (int i = 0, s = 0; i < nums1.size(); ++i) {
            s1 += nums1[i];
            s = max(s + nums2[i] - nums1[i], 0);
            maxSum = max(maxSum, s);
        }
        return s1 + maxSum;
    }

public:
    int maximumsSplicedArray(vector<int> &nums1, vector<int> &nums2) {
        return max(solve(nums1, nums2), solve(nums2, nums1));
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func solve(nums1, nums2 []int) int {
	s1, maxSum, s := 0, 0, 0
	for i, x := range nums1 {
		s1 += x
		s = max(s+nums2[i]-x, 0)
		maxSum = max(maxSum, s)
	}
	return s1 + maxSum
}

func maximumsSplicedArray(nums1, nums2 []int) int {
	return max(solve(nums1, nums2), solve(nums2, nums1))
}

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

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。仅需要几个额外的变量。
 Comments
On this page
2321-拼接数组的最大分数