Skip to main content
Talentd

Maximum Score Of Spliced Array - Solution & Explanation

HardArrayDynamic Programming15 min readAsked at: Microsoft
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given two arrays of equal length. You may choose a single subarray and swap it between the arrays. The goal is to maximize the final sum of either array after the splice. The challenge is identifying which segment swap produces the largest increase.

The key observation: swapping a segment does not change both arrays independently. Instead, it transfers the difference between elements in that segment. If you track how much benefit each position gives when swapped, the task reduces to finding a maximum gain subarray.

Approach 1: Dynamic Programming on Difference Array (Kadane) (Time: O(n), Space: O(1))

Compute the base sums of both arrays first. If you swap a segment from nums2 into nums1, the gain at index i becomes nums2[i] - nums1[i]. Build this implicit difference while iterating and apply Kadane's algorithm to find the maximum subarray sum. That value represents the best possible improvement to sum(nums1). Repeat the same process in the opposite direction using nums1[i] - nums2[i] to see if improving nums2 yields a larger result. The final answer is the maximum of both improved sums. The algorithm scans the arrays once and maintains a running maximum gain, so it runs in O(n) time with O(1) space.

This approach works because any valid splice corresponds exactly to a contiguous segment. Kadane's algorithm efficiently identifies the segment where the cumulative difference produces the highest gain.

Approach 2: Greedy Difference Tracking (Time: O(n), Space: O(1))

The same idea can be implemented using a greedy running-gain tracker rather than explicitly describing it as dynamic programming. While iterating through the arrays, compute the difference between elements and maintain a running gain. If the running gain becomes negative, reset it because continuing the segment would only reduce the final score. Track the maximum gain encountered during the scan. Perform this process twice: once assuming you improve nums1 and once assuming you improve nums2. Each pass evaluates whether starting a new splice or extending the current one produces a better result.

This greedy interpretation is essentially Kadane's algorithm but framed as continuously deciding whether to extend the current splice segment or start a new one. It avoids storing additional arrays and only tracks a few running variables.

Conceptually, the problem blends ideas from Array manipulation and maximum subarray problems commonly solved with Dynamic Programming or Greedy strategies.

Recommended for interviews: The Kadane-based dynamic programming approach is what interviewers expect. It shows you can transform the swap operation into a difference-gain problem and apply a classic maximum subarray algorithm. Starting with the naive thought process about swapping segments demonstrates understanding, but recognizing the Kadane reduction shows strong problem-solving skills.

Approach 1: Dynamic Programming Approach

We'll use a dynamic programming-like approach to evaluate the effect on the scores of swapping subarrays of nums1 with nums2 and vice-versa. By maintaining effective difference arrays, we can decide whether to swap segments to increase the overall array scores.

This solution calculates the sum of elements in each list. It then considers potential subarray swap benefits using a sliding window difference approach (similar to Kadane's algorithm). It iterates over the list, maintaining current maximum difference sums to calculate the best swap improvement for either direction (nums1 to nums2 and vice-versa).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input arrays as they are traversed linearly.
Space Complexity: O(1), as constant extra space is used.
Try this approach in the editor →

Approach 2: Greedy Approach Using Difference Tracking

This approach involves calculating the sum of the original arrays and determining benefits from swapping segments. A direct greedy evaluation of swapping possibilities at individual positions and maintaining optimal cumulative benefits guides decision-making correlations for the final score estimate.

This implementation uses two primary gain measures to note when swaps benefit either array, consistently comparing accumulated gain values. The logic operates linearly due to orderly swaps and maximized potential differences checked per item.

Code

CPythonJavaPythonC#JavaScript

C

Python

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), reliant on linear assessments per index.
Space Complexity: O(1), nobvizationalized auxiliary computations.
Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming ApproachTime Complexity: O(n), where n is the length of the input arrays as they are traversed linearly.
Space Complexity: O(1), as constant extra space is used.
Greedy Approach Using Difference TrackingTime Complexity: O(n), reliant on linear assessments per index.
Space Complexity: O(1), nobvizationalized auxiliary computations.
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (Kadane on Difference)O(n)O(1)Best general solution. Converts splice benefit into a maximum subarray problem.
Greedy Difference TrackingO(n)O(1)Same optimal logic implemented with a running gain reset strategy.
Bidirectional Gain EvaluationO(n)O(1)Evaluate improvements for both arrays separately to ensure the best final score.

Video Solution

Leetcode 2321. Maximum Score Of Spliced Array | Hindi • ThinkCode • 2,428 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Score Of Spliced Array easy or hard?
Maximum Score Of Spliced Array is rated Hard on LeetCode because the splice operation hides a maximum subarray transformation. Once the difference-array insight is recognized, the implementation becomes straightforward using Kadane's algorithm.
Maximum Score Of Spliced Array Python/Java solution
Python and Java implementations follow the same logic: compute array sums, iterate through differences, maintain a running maximum subarray gain, and update the best improvement. The algorithm remains O(n) with constant space across all languages including C++, C, and JavaScript.
How to solve Maximum Score Of Spliced Array in O(n)?
First compute the sum of both arrays. Then iterate while calculating the difference nums2[i] - nums1[i] and apply Kadane's algorithm to find the maximum gain segment for improving nums1. Repeat with nums1[i] - nums2[i] to check improvement for nums2. Add the best gain to the respective base sum and return the maximum result.
What is the best approach for Maximum Score Of Spliced Array?
The optimal solution uses Kadane's algorithm on a difference array. Compute the gain of swapping each index (nums2[i] - nums1[i]) and find the maximum subarray sum to determine the best splice segment. Repeat the process in the opposite direction. This runs in O(n) time and O(1) space.
Is Maximum Score Of Spliced Array asked at Google/Amazon/Meta?
Maximum Score Of Spliced Array follows a classic maximum subarray transformation pattern often seen in interviews at companies like Amazon, Google, and Meta. The problem tests recognition of Kadane's algorithm and the ability to convert operations into a gain-based array problem.
What data structure is used in Maximum Score Of Spliced Array?
The solution primarily uses arrays and running variables. The key technique is applying Kadane's algorithm on element-wise differences between the two arrays rather than using additional data structures.
What is the time complexity of Maximum Score Of Spliced Array?
The optimal algorithm runs in O(n) time because it scans the arrays once while maintaining a running maximum gain using Kadane's algorithm. Space complexity is O(1) since only a few variables are tracked during iteration.

Ready to solve this problem?

Practice Maximum Score Of Spliced Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Subarray