题目描述

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 <= 105
  • 1 <= nums1[i], nums2[i] <= 104

题解——滑动窗口

思路

滑动窗口,记录改变一个窗口对原数组的增益,只要change>=0,就有可能产生最优解,可以继续下去

如果change<0,说明已经找过的部分产生了**负面效果**,应当舍弃,此时找到第一个使change>=0的位置继续查找

由于nums1和nums2都可能为基,我们要查找两次

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int change=0,i=0,j=0,sz=nums1.size(),maxchange1=0,maxchange2=0;
        int sum1=accumulate(nums1.begin(),nums1.end(),0),sum2=accumulate(nums2.begin(),nums2.end(),0);
        while(j<sz)//以nums1为基
        {
            if(change>=0)
            {
                change+=nums2[j]-nums1[j];
                ++j;
            }
            else
                while(change<0)
                {
                    change-=nums2[i]-nums1[i];
                    ++i;
                }
            maxchange1=max(change,maxchange1);
        }
        change=i=j=0;
        while(j<sz)//以nums2为基
        {
            if(change>=0)
            {
                change+=nums1[j]-nums2[j];
                ++j;
            }
            else
                while(change<0)
                {
                    change-=nums1[i]-nums2[i];
                    ++i;
                }
            maxchange2=max(change,maxchange2);
        }
        return max(sum1+maxchange1,sum2+maxchange2);
    }
};