你提供的代码是 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)。

如果需要,也可以用一次遍历同时维护最大和最小子数组和,代码已完美实现。

如果还有疑问(例如边界条件、为什么不直接枚举子数组),欢迎继续讨论!

 

Logo

汇聚全球AI编程工具,助力开发者即刻编程。

更多推荐