Maximum Score Of Spliced Array

Created 06/25/2022

Leetcode

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,12,13,4,5] and nums2 becomes [11,2,3,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).

Example 1:

Input: nums1 = [60,60,60], nums2 = [10,90,10]
Output: 210
Explanation: Choosing left = 1 and right = 1, we have nums1 = [60,90,60] and nums2 = [10,60,10].
The score is max(sum(nums1), sum(nums2)) = max(210, 80) = 210.

Example 2:

Input: nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]
Output: 220
Explanation: Choosing left = 3, right = 4, we have nums1 = [20,40,20,40,20] and nums2 = [50,20,50,70,30].
The score is max(sum(nums1), sum(nums2)) = max(140, 220) = 220.

Example 3:

Input: nums1 = [7,11,13], nums2 = [1,1,1]
Output: 31
Explanation: We choose not to swap any subarray.
The score is max(sum(nums1), sum(nums2)) = max(31, 3) = 31.

Constraints:

• n == nums1.length == nums2.length

• 1 <= n <= 105

• 1 <= nums1[i], nums2[i] <= 104

Basic Idea

主要题意是选择两个边界left和right，然后将nums1和nums2的边界内的部分互换，只换一次。求这样操作互换后的nums1和nums2的可能的和的最大值。

因为数据量比较大，只能进行 O(n) 的操作。想到可以利用前缀和，先算出nums1和nums2的前缀和，然后将两个前缀和数组相减，就可以的到一个前缀和的差diff array，diff[right] - diff[left] 的物理意义是 [left~right] 这一段中nums1的和与nums2的和的差。得到diff array之后，只需要求出所有可能的diff[right]-diff[left] 的最大值和最小值即可。其中如果最大值为正，则说明将这段从nums1中换到nums2可以令nums2的和增加到最大，如果最小值为负，则说明这段换到nums1中可以让nums1的和增加到最大。最终返回的就是交换后的两个和中较大的。

Java Code

class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        int l = nums1.length;
        int[] preSum1 = new int[l + 1];
        int[] preSum2 = new int[l + 1];
        for (int i = 0; i < l; ++i) {
            preSum1[i + 1] = preSum1[i] + nums1[i];
            preSum2[i + 1] = preSum2[i] + nums2[i];
        }
        int[] diff = new int[l];
        for (int i = 0; i < l; ++i) {
            diff[i] = preSum1[i + 1] - preSum2[i + 1];
        }
        int minNegDiff = Integer.MAX_VALUE, maxPosDiff = Integer.MIN_VALUE;
        int min = diff[0], max = diff[0];
        for (int i = 1; i < l; ++i) {
            minNegDiff = Math.min(minNegDiff, diff[i] - max);
            maxPosDiff = Math.max(maxPosDiff, diff[i] - min);
            min = Math.min(min, diff[i]);
            max = Math.max(max, diff[i]);
        }
        int candidate1 = minNegDiff < 0 ? preSum1[l] - minNegDiff : preSum1[l];
        int candidate2 = maxPosDiff > 0 ? preSum2[l] + maxPosDiff : preSum2[l];
        return Math.max(candidate1, candidate2);
    }
}