LeetCode 题解工作台
拼接数组的最大分数
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度都是 n 。 你可以选择两个整数 left 和 right ，其中 0 ，接着 交换 两个子数组 nums1[left...right] 和 nums2[left...right] 。 例如，设 nums1 = [1,2,3,4,…
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
class Solution: def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个下标从 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.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 104
解题思路
方法一
class Solution:
def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
def f(nums1, nums2):
d = [a - b for a, b in zip(nums1, nums2)]
t = mx = d[0]
for v in d[1:]:
if t > 0:
t += v
else:
t = v
mx = max(mx, t)
return mx
s1, s2 = sum(nums1), sum(nums2)
return max(s2 + f(nums1, nums2), s1 + f(nums2, nums1))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of possible subarrays, which can be O(n^2) without optimization. However, by using dynamic programming and cumulative sums, the solution can be optimized to O(n), reducing unnecessary recalculations. Space complexity depends on the storage needed for the cumulative sums and intermediate states, typically O(n). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Evaluating knowledge of dynamic programming with state transitions.
- question_mark
Ability to optimize through cumulative sums and subarray manipulation.
- question_mark
Assessment of problem-solving efficiency, particularly with large input sizes.
常见陷阱
外企场景- error
Not recognizing the importance of cumulative sums for efficient score computation.
- error
Failing to account for the possibility of no swap being optimal.
- error
Overcomplicating the problem by considering unnecessary subarrays or operations.
进阶变体
外企场景- arrow_right_alt
What if the arrays have different lengths?
- arrow_right_alt
How would this change if negative numbers were allowed in the arrays?
- arrow_right_alt
What if the swap operation could be applied multiple times?