2321. Maximum Score Of Spliced Array

Question

You are given two 0-indexed integer arrays nums1 and nums2, both of length n.

You can choose two integers left and right where 0 <= left <= right < n and swap the subarray nums1[left...right] with the subarray nums2[left...right].

• For example, if nums1 = [1,2,3,4,5] and nums2 = [11,12,13,14,15] and you choose left = 1 and right = 2, nums1 becomes [1,<strong><u>12,13</u></strong>,4,5] and nums2 becomes [11,<strong><u>2,3</u></strong>,14,15].

You may choose to apply the mentioned operation once or not do anything.

The score of the arrays is the maximum of sum(nums1) and sum(nums2), where sum(arr) is the sum of all the elements in the array arr.

Return the maximum possible score.

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Solution

滑动窗口。一开始想用dp解决的。
后来发现可以优化到直接记录连续的最大差值即可。
以后有提到连续的一定要想到滑动窗口实现。

辅助方法getMinContigouousDiff()用来计算两个数组间连续的最小的差值和。
当sum为负数时，窗口向右侧扩展，将新的位置加入sum，并更新最小值min。
当扩展后sum大于0时，则放弃之前的所有元素，将sum归零。
最后返回最小值min。

计算两个数组的所有数字之和t1和t2。分别计算nums1[]和nums2[]的差min1和nums2[]和nums1[]的差min2。
在其中替换连续的部分则为t1-min1，t2-min2。取两者中较大的数字返回即可。

Code

class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int t1 = 0, t2 = 0;
        for(int i = 0; i < n ;i++){ //计算两个数组未替换前的和
            t1 += nums1[i];
            t2 += nums2[i];
        }
        int min1 = getMinContiguousDiff(nums2, nums1);
        int min2 = getMinContiguousDiff(nums1, nums2);
        return Math.max(t1 - min1, t2 - min2);  //替换连续的部分，两者中取最大值
    }
    
    private int getMinContiguousDiff(int[] nums1, int[] nums2){ //滑动窗口，求连续元素间的最小差值
        int sum = 0, min = 0;
        for(int i = 0; i < nums1.length; i++){
            if(sum <= 0){   //当sum为负数时，窗口向右侧扩展，将新的位置加入sum
                int diff = nums2[i] - nums1[i];
                sum += diff;
                if(diff < 0) min = Math.min(min, sum);  //更新最小值
                if(sum > 0) sum = 0;    //当sum为正数时，抛弃前面的元素，重新开始计算sum
            }
        }
        return min;
    }
}