DeepSeek LeetCode 2321.拼接数组的最大分数 public int maximumsSplicedArray(int[] nums1, int[] nums2)
你提供的代码是 LeetCode 2321「拼接数组的最大分数」的正确解法。
下面简单解释一下思路:
· 记原数组的和为 sum1 = sum(nums1), sum2 = sum(nums2)。
· 如果要提高 nums1 的总分,可以交换一段子数组 [l, r],交换后 nums1 的新总和为:
```
sum1 + (nums2[l..r] 的和 - nums1[l..r] 的和) = sum1 + sum(diff[l..r])
其中 diff[i] = nums2[i] - nums1[i]
```
所以我们要找 diff 的 最大子数组和(可以为空,即不交换)。
· 同理,提高 nums2 的总分时,新总和为:
```
sum2 - (nums1[l..r] 的和 - nums2[l..r] 的和) = sum2 - sum(diff[l..r])
```
此时要找 diff 的 最小子数组和(可以为空)。
· 最终答案是 max(sum1 + maxSubArray, sum2 - minSubArray)。
你的代码:
class Solution {
public int maximumsSplicedArray(int[] nums1, int[] nums2) {
int n = nums1.length;
long sum1 = 0, sum2 = 0;
long maxEnding = 0, maxSoFar = 0; // 最大子数组和(允许空子数组)
long minEnding = 0, minSoFar = 0; // 最小子数组和(允许空子数组)
for (int i = 0; i < n; i++) {
sum1 += nums1[i];
sum2 += nums2[i];
int diff = nums2[i] - nums1[i];
// 计算 diff 的最大子数组和
maxEnding = Math.max(0, maxEnding + diff);
maxSoFar = Math.max(maxSoFar, maxEnding);
// 计算 diff 的最小子数组和
minEnding = Math.min(0, minEnding + diff);
minSoFar = Math.min(minSoFar, minEnding);
}
// 两种情况:让 nums1 变大或让 nums2 变大
long ans = Math.max(sum1 + maxSoFar, sum2 - minSoFar);
return (int) ans;
}
}
· 用 maxEnding 和 maxSoFar 计算最大子数组和(允许空 → 与0取max)。
· 用 minEnding 和 minSoFar 计算最小子数组和(允许空 → 与0取min)。
· 最后返回 Math.max(sum1 + maxSoFar, sum2 - minSoFar)。
✅ 正确性:
· 题干允许交换任意一个连续子数组(包括空),因此最大/最小子数组和可以为0,表示不交换。
· 使用 long 类型避免求和溢出。
· 算法时间复杂度 O(n),空间 O(1)。
如果需要,也可以用一次遍历同时维护最大和最小子数组和,代码已完美实现。
如果还有疑问(例如边界条件、为什么不直接枚举子数组),欢迎继续讨论!
更多推荐





所有评论(0)