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].
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.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 104The key idea in #2321 Maximum Score Of Spliced Array is to maximize the total sum of one array after optionally swapping a single contiguous subarray between two arrays of equal length. Instead of simulating every possible swap, we analyze the net gain produced by swapping segments.
Start by computing the base sums of both arrays. Then observe that swapping elements effectively changes the sum by the difference between corresponding values. By transforming this into a difference array, the task becomes finding the maximum subarray gain that could be added to the original sum.
This is efficiently solved using a variation of Kadane’s Algorithm from dynamic programming. We evaluate the best gain for swapping from the second array into the first, and vice versa, then take the maximum possible final score.
This approach avoids brute-force segment checks and runs in O(n) time with O(1) extra space, making it suitable for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Difference Array + Kadane's Algorithm | O(n) | O(1) |
ThinkCode
Use these hints if you're stuck. Try solving on your own first.
Think on Dynamic Programming.
First assume you will be taking the array a and choose some subarray from b
Suppose the DP is DP(pos, state). pos is the current position you are in. state is one of {0,1,2}, where 0 means taking the array a, 1 means we are taking the subarray b, and 2 means we are again taking the array a. We need to handle the transitions carefully.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Kadane’s Algorithm helps identify the maximum contiguous gain in the difference array created from the two input arrays. This directly corresponds to the best subarray segment to swap for maximizing the final score.
Yes, problems involving subarray optimization and Kadane’s Algorithm variations are common in FAANG-style interviews. This question tests understanding of dynamic programming and array transformation techniques.
No advanced data structures are required. Arrays and a few running variables are sufficient since the core logic relies on computing differences and applying Kadane’s dynamic programming technique.
The optimal approach converts the swap operation into a gain/loss problem using a difference array. Then Kadane’s Algorithm is applied to find the maximum subarray gain that improves the total score. This reduces the problem to linear time.