Problem

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

Examples

Example 1

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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 <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^4

Solution

Method 1 – Kadane’s Algorithm for Maximum Subarray Gain

Intuition

To maximize the score, we can swap a subarray between nums1 and nums2. The best swap is the one that maximizes the increase in sum for one array (and decrease for the other). This is equivalent to finding the subarray where the difference between nums2 and nums1 (or vice versa) is maximized. We use Kadane’s algorithm to find the maximum gain for both directions and take the best possible result.

Approach

  1. Compute the sum of nums1 and nums2.
  2. For both directions (swapping from nums2 to nums1 and from nums1 to nums2):
    • Compute the difference array (nums2[i] - nums1[i]) or (nums1[i] - nums2[i]).
    • Use Kadane’s algorithm to find the maximum subarray sum (the best gain).
    • Add this gain to the original sum of the target array.
  3. Return the maximum of the two possible results.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
        int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
        int gain1 = 0, cur1 = 0, gain2 = 0, cur2 = 0;
        for (int i = 0; i < nums1.size(); ++i) {
            cur1 = max(nums2[i] - nums1[i], cur1 + nums2[i] - nums1[i]);
            gain1 = max(gain1, cur1);
            cur2 = max(nums1[i] - nums2[i], cur2 + nums1[i] - nums2[i]);
            gain2 = max(gain2, cur2);
        }
        return max(sum1 + gain1, sum2 + gain2);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func maximumsSplicedArray(nums1, nums2 []int) int {
    sum1, sum2 := 0, 0
    for i := range nums1 {
        sum1 += nums1[i]
        sum2 += nums2[i]
    }
    gain1, cur1, gain2, cur2 := 0, 0, 0, 0
    for i := range nums1 {
        d1 := nums2[i] - nums1[i]
        cur1 = max(d1, cur1+d1)
        gain1 = max(gain1, cur1)
        d2 := nums1[i] - nums2[i]
        cur2 = max(d2, cur2+d2)
        gain2 = max(gain2, cur2)
    }
    return max(sum1+gain1, sum2+gain2)
}
func max(a, b int) int { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        int sum1 = 0, sum2 = 0;
        for (int i = 0; i < nums1.length; i++) {
            sum1 += nums1[i];
            sum2 += nums2[i];
        }
        int gain1 = 0, cur1 = 0, gain2 = 0, cur2 = 0;
        for (int i = 0; i < nums1.length; i++) {
            cur1 = Math.max(nums2[i] - nums1[i], cur1 + nums2[i] - nums1[i]);
            gain1 = Math.max(gain1, cur1);
            cur2 = Math.max(nums1[i] - nums2[i], cur2 + nums1[i] - nums2[i]);
            gain2 = Math.max(gain2, cur2);
        }
        return Math.max(sum1 + gain1, sum2 + gain2);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun maximumsSplicedArray(nums1: IntArray, nums2: IntArray): Int {
        val sum1 = nums1.sum()
        val sum2 = nums2.sum()
        var gain1 = 0; var cur1 = 0; var gain2 = 0; var cur2 = 0
        for (i in nums1.indices) {
            cur1 = maxOf(nums2[i] - nums1[i], cur1 + nums2[i] - nums1[i])
            gain1 = maxOf(gain1, cur1)
            cur2 = maxOf(nums1[i] - nums2[i], cur2 + nums1[i] - nums2[i])
            gain2 = maxOf(gain2, cur2)
        }
        return maxOf(sum1 + gain1, sum2 + gain2)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def maximumsSplicedArray(self, nums1: list[int], nums2: list[int]) -> int:
        sum1, sum2 = sum(nums1), sum(nums2)
        gain1 = gain2 = cur1 = cur2 = 0
        for a, b in zip(nums1, nums2):
            cur1 = max(b - a, cur1 + b - a)
            gain1 = max(gain1, cur1)
            cur2 = max(a - b, cur2 + a - b)
            gain2 = max(gain2, cur2)
        return max(sum1 + gain1, sum2 + gain2)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn maximums_spliced_array(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let sum1: i32 = nums1.iter().sum();
        let sum2: i32 = nums2.iter().sum();
        let (mut gain1, mut cur1, mut gain2, mut cur2) = (0, 0, 0, 0);
        for i in 0..nums1.len() {
            cur1 = (nums2[i] - nums1[i]).max(cur1 + nums2[i] - nums1[i]);
            gain1 = gain1.max(cur1);
            cur2 = (nums1[i] - nums2[i]).max(cur2 + nums1[i] - nums2[i]);
            gain2 = gain2.max(cur2);
        }
        sum1.max(sum1 + gain1).max(sum2 + gain2)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    maximumsSplicedArray(nums1: number[], nums2: number[]): number {
        const sum1 = nums1.reduce((a, b) => a + b, 0);
        const sum2 = nums2.reduce((a, b) => a + b, 0);
        let gain1 = 0, cur1 = 0, gain2 = 0, cur2 = 0;
        for (let i = 0; i < nums1.length; i++) {
            cur1 = Math.max(nums2[i] - nums1[i], cur1 + nums2[i] - nums1[i]);
            gain1 = Math.max(gain1, cur1);
            cur2 = Math.max(nums1[i] - nums2[i], cur2 + nums1[i] - nums2[i]);
            gain2 = Math.max(gain2, cur2);
        }
        return Math.max(sum1 + gain1, sum2 + gain2);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the arrays. We scan the arrays a constant number of times.
  • 🧺 Space complexity: O(1), only a few variables are used.