本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

LeetCode2321. 拼接数组的最大分数

给你两个下标从 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 <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁴

最大子段和

构建有n个元素的数组nums3，nums3[i] = nums2[i]-nums1[i]。如果nums3的最大子段和为：x，则将替换后，nums1的最大值为：原始num1的和+x。
如果x < 0，则不替换。
让nums2最大的原理，类似。

代码

核心代码

class Solution {
		public:
			int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
				auto Do = [](vector<int>& nums1, vector<int>& nums2) {
					const int x = accumulate(nums1.begin(), nums1.end(), 0);
					vector<int> nums;
					for (int i = 0; i < nums1.size(); i++) {
						nums.emplace_back(nums2[i] - nums1[i]);
					}
					int pre = 0, sum = 0, ans = INT_MIN;
					for (const auto& i : nums) {
						sum += i;
						pre = min(pre, sum);
						ans = max(ans, sum - pre);
					}
					return x + ans;
				};
				return max(Do(nums1, nums2), Do(nums2, nums1));
			}
		};

单元测试

vector<int> nums1, nums2;
		TEST_METHOD(TestMethod11)
		{
			nums1 = { 60, 60, 60 }, nums2 = { 10, 90, 10 };
			auto res = Solution().maximumsSplicedArray(nums1, nums2);
			AssertEx(210, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums1 = { 20,40,20,70,30 }, nums2 = { 50,20,50,40,20 };
			auto res = Solution().maximumsSplicedArray(nums1, nums2);
			AssertEx(220, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums1 = { 7,11,13 }, nums2 = { 1,1,1};
			auto res = Solution().maximumsSplicedArray(nums1, nums2);
			AssertEx(31, res);
		}