Question

2321. 拼接数组的最大分数

English Version

题目描述

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

解法

方法一

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))

class Solution {
  public int maximumsSplicedArray(int[] nums1, int[] nums2) {
    int s1 = 0, s2 = 0, n = nums1.length;
    for (int i = 0; i < n; ++i) {
      s1 += nums1[i];
      s2 += nums2[i];
    }
    return Math.max(s2 + f(nums1, nums2), s1 + f(nums2, nums1));
  }

  private int f(int[] nums1, int[] nums2) {
    int t = nums1[0] - nums2[0];
    int mx = t;
    for (int i = 1; i < nums1.length; ++i) {
      int v = nums1[i] - nums2[i];
      if (t > 0) {
        t += v;
      } else {
        t = v;
      }
      mx = Math.max(mx, t);
    }
    return mx;
  }
}

class Solution {
public:
  int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
    int s1 = 0, s2 = 0, n = nums1.size();
    for (int i = 0; i < n; ++i) {
      s1 += nums1[i];
      s2 += nums2[i];
    }
    return max(s2 + f(nums1, nums2), s1 + f(nums2, nums1));
  }

  int f(vector<int>& nums1, vector<int>& nums2) {
    int t = nums1[0] - nums2[0];
    int mx = t;
    for (int i = 1; i < nums1.size(); ++i) {
      int v = nums1[i] - nums2[i];
      if (t > 0)
        t += v;
      else
        t = v;
      mx = max(mx, t);
    }
    return mx;
  }
};

func maximumsSplicedArray(nums1 []int, nums2 []int) int {
  s1, s2 := 0, 0
  n := len(nums1)
  for i, v := range nums1 {
    s1 += v
    s2 += nums2[i]
  }
  f := func(nums1, nums2 []int) int {
    t := nums1[0] - nums2[0]
    mx := t
    for i := 1; i < n; i++ {
      v := nums1[i] - nums2[i]
      if t > 0 {
        t += v
      } else {
        t = v
      }
      mx = max(mx, t)
    }
    return mx
  }
  return max(s2+f(nums1, nums2), s1+f(nums2, nums1))
}