Maximum Score Of Spliced Array
HardPrompt
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]andnums2 = [11,12,13,14,15]and you chooseleft = 1andright = 2,nums1becomes[1,12,13,4,5]andnums2becomes[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] <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible subarray swap. It iterates through all possible start (left) and end (right) indices of the subarray to be swapped. For each subarray, it calculates the sum of elements to be swapped, computes the new sums of nums1 and nums2, and updates the maximum score found so far.
Algorithm
- Calculate the initial sums of
nums1andnums2, let them besum1andsum2. - Initialize
maxScorewithmax(sum1, sum2). This handles the case of not performing any swap. - Use a nested loop to iterate through all possible start (
left) and end (right) indices of a subarray, where0 <= left <= right < n. - For each
(left, right)pair, use a third loop to calculate the sum of the subarraynums1[left...right](sub1Sum) andnums2[left...right](sub2Sum). - Calculate the new sums of the arrays after the hypothetical swap:
newSum1 = sum1 - sub1Sum + sub2SumnewSum2 = sum2 - sub2Sum + sub1Sum
- Update
maxScoreby taking the maximum of its current value,newSum1, andnewSum2. - After checking all possible subarrays, return
maxScore.
Walkthrough
The algorithm starts by calculating the initial sums of nums1 and nums2. The maximum of these two sums serves as the initial max_score, covering the case where no swap is performed. It then enters a nested loop structure. The outer loop iterates left from 0 to n-1, and the middle loop iterates right from left to n-1. These two loops define the subarray [left...right]. Inside these loops, a third loop runs from left to right to calculate sub1_sum (sum of nums1[left...right]) and sub2_sum (sum of nums2[left...right]). After getting the subarray sums, the new total sums for nums1 and nums2 are calculated. The max_score is then updated with the maximum of its current value and the two new sums. After all possible subarrays are checked, the final max_score is returned.
class Solution { public int maximumsSplicedArray(int[] nums1, int[] nums2) { int n = nums1.length; long sum1 = 0, sum2 = 0; for (int x : nums1) sum1 += x; for (int x : nums2) sum2 += x; long maxScore = Math.max(sum1, sum2); for (int left = 0; left < n; left++) { for (int right = left; right < n; right++) { long sub1Sum = 0; long sub2Sum = 0; for (int k = left; k <= right; k++) { sub1Sum += nums1[k]; sub2Sum += nums2[k]; } long newSum1 = sum1 - sub1Sum + sub2Sum; long newSum2 = sum2 - sub2Sum + sub1Sum; maxScore = Math.max(maxScore, Math.max(newSum1, newSum2)); } } return (int) maxScore; }}Complexity
Time
O(n^3), where n is the length of the arrays. There are two nested loops to generate O(n^2) subarrays, and for each subarray, we iterate through its elements to calculate the sum, which takes O(n) time in the worst case.
Space
O(1), as we only use a few variables to store sums and indices, not dependent on the input size.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for small inputs.
Cons
Extremely inefficient due to the cubic time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints (n up to 10^5).
This approach is an optimization of the brute force method. Instead of recalculating the subarray sum from scratch in an innermost loop, it maintains a running sum of the current subarray as it extends the subarray's right boundary. This eliminates one loop, reducing the complexity from cubic to quadratic.
Algorithm
- Calculate the initial sums of
nums1andnums2, let them besum1andsum2. - Initialize
maxScorewithmax(sum1, sum2). - Use an outer loop to iterate through all possible start indices (
left) from0ton-1. - Inside the outer loop, initialize running sums for the current subarray,
sub1Sum = 0andsub2Sum = 0. - Use an inner loop to iterate through all possible end indices (
right) fromleftton-1. - In the inner loop, update the running sums by adding the current elements:
sub1Sum += nums1[right]andsub2Sum += nums2[right]. - Calculate the new total sums
newSum1andnewSum2using the running subarray sums. - Update
maxScorewith the maximum of its current value,newSum1, andnewSum2. - Return
maxScoreafter the loops complete.
Walkthrough
Similar to the previous approach, we first calculate the initial sums and initialize max_score. The algorithm then uses two nested loops to iterate through all possible subarrays. The outer loop fixes the left index. The inner loop iterates right from left to n-1. Inside this loop, we maintain sub1_sum and sub2_sum for the current subarray [left...right]. When right increments, we just add nums1[right] and nums2[right] to these running sums, avoiding a full recalculation. For each (left, right) pair, we calculate the potential new scores and update max_score accordingly.
class Solution { public int maximumsSplicedArray(int[] nums1, int[] nums2) { int n = nums1.length; long sum1 = 0, sum2 = 0; for (int x : nums1) sum1 += x; for (int x : nums2) sum2 += x; long maxScore = Math.max(sum1, sum2); for (int left = 0; left < n; left++) { long sub1Sum = 0; long sub2Sum = 0; for (int right = left; right < n; right++) { sub1Sum += nums1[right]; sub2Sum += nums2[right]; long newSum1 = sum1 - sub1Sum + sub2Sum; long newSum2 = sum2 - sub2Sum + sub1Sum; maxScore = Math.max(maxScore, Math.max(newSum1, newSum2)); } } return (int) maxScore; }}Complexity
Time
O(n^2), where n is the length of the arrays. The two nested loops result in a quadratic number of iterations.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
More efficient than the triple loop brute force.
Still relatively easy to conceptualize.
Cons
Still too slow for the given constraints, leading to 'Time Limit Exceeded'.
This is the most efficient approach. It reframes the problem into two independent "Maximum Subarray Sum" problems, which can be solved in linear time using Kadane's algorithm. By analyzing the effect of a swap on the total sum of an array, we can see that the change in sum is equal to the sum of a subarray in a newly formed difference array. Maximizing this change is a classic problem solvable with Kadane's algorithm.
Algorithm
- The problem can be split into two subproblems: maximizing the sum of
nums1and maximizing the sum ofnums2. - To maximize
sum(nums1), we need to find a subarray[l..r]that maximizes the gain from the swap. The new sum issum(nums1) + sum(nums2[l..r]) - sum(nums1[l..r]). This is equivalent tosum(nums1) + sum(diff[l..r])wherediff[i] = nums2[i] - nums1[i]. So, we need to find the maximum subarray sum of this difference array. - Similarly, to maximize
sum(nums2), we need to find the maximum subarray sum of the difference arraydiff[i] = nums1[i] - nums2[i]. - Both maximum subarray sum problems can be solved using Kadane's algorithm in linear time.
- The algorithm proceeds as follows:
a. Calculate the initial sums
sum1andsum2. b. Apply Kadane's algorithm to find the maximum gain fornums1(fromnums2[i] - nums1[i]). Add this gain tosum1to get a potential maximum score. c. Apply Kadane's algorithm to find the maximum gain fornums2(fromnums1[i] - nums2[i]). Add this gain tosum2to get another potential maximum score. d. The final answer is the maximum of these two potential scores. - Kadane's algorithm: Initialize
maxGain = 0andcurrentGain = 0. Iterate through the array, adding the current element's difference tocurrentGain. UpdatemaxGainwithmax(maxGain, currentGain). IfcurrentGainbecomes negative, reset it to 0.
Walkthrough
Let S1 be the sum of nums1 and S2 be the sum of nums2. If we swap nums1[l..r] with nums2[l..r], the new sum of nums1 becomes S1 - sum(nums1[l..r]) + sum(nums2[l..r]). This can be rewritten as S1 + sum(nums2[i] - nums1[i]) for i from l to r. To maximize the new sum of nums1, we need to find the subarray [l..r] that maximizes the gain, which is sum(nums2[i] - nums1[i]). This is a classic Maximum Subarray Sum problem on the difference array diff[i] = nums2[i] - nums1[i]. Similarly, to maximize the new sum of nums2, we need to find the maximum subarray sum of the difference array diff[i] = nums1[i] - nums2[i]. We can solve both of these using Kadane's algorithm and take the maximum of the two resulting scores. The case of not swapping is handled naturally by Kadane's algorithm if we initialize the maximum gain to 0, as an empty subarray swap results in a gain of 0.
class Solution { public int maximumsSplicedArray(int[] nums1, int[] nums2) { int n = nums1.length; long sum1 = 0, sum2 = 0; for (int x : nums1) sum1 += x; for (int x : nums2) sum2 += x; // Case 1: Maximize sum of nums1 by swapping with a subarray from nums2. // This is equivalent to finding the maximum subarray sum of (nums2[i] - nums1[i]). long maxGain1 = 0; long currentGain1 = 0; for (int i = 0; i < n; i++) { currentGain1 += nums2[i] - nums1[i]; if (currentGain1 < 0) { currentGain1 = 0; } maxGain1 = Math.max(maxGain1, currentGain1); } long ans1 = sum1 + maxGain1; // Case 2: Maximize sum of nums2 by swapping with a subarray from nums1. // This is equivalent to finding the maximum subarray sum of (nums1[i] - nums2[i]). long maxGain2 = 0; long currentGain2 = 0; for (int i = 0; i < n; i++) { currentGain2 += nums1[i] - nums2[i]; if (currentGain2 < 0) { currentGain2 = 0; } maxGain2 = Math.max(maxGain2, currentGain2); } long ans2 = sum2 + maxGain2; return (int) Math.max(ans1, ans2); }}Complexity
Time
O(n). We perform a few single passes over the arrays. Calculating initial sums takes O(n), and each application of Kadane's algorithm also takes O(n). The total time complexity is linear.
Space
O(1). No extra space proportional to the input size is used. The difference values are calculated on-the-fly.
Trade-offs
Pros
Optimal time complexity, making it very efficient for large inputs.
Optimal space complexity.
Cons
The logic is less direct and requires recognizing the connection to the Maximum Subarray Sum problem.
Solutions
Solution
class Solution {public int maximumsSplicedArray(int[] nums1, int[] nums2) { int s1 = 0, s2 = 0, n = nums1.length; for (int i = 0; i < n; ++i) { s1 += nums1[i]; s2 += nums2[i]; } return Math.max(s2 + f(nums1, nums2), s1 + f(nums2, nums1)); }private int f(int[] nums1, int[] nums2) { int t = nums1[0] - nums2[0]; int mx = t; for (int i = 1; i < nums1.length; ++i) { int v = nums1[i] - nums2[i]; if (t > 0) { t += v; } else { t = v; } mx = Math.max(mx, t); } return mx; }}class Solution {public: int maximumsSplicedArray(vector<int> &nums1, vector<int> &nums2) { int s1 = 0, s2 = 0, n = nums1.size(); for (int i = 0; i < n; ++i) { s1 += nums1[i]; s2 += nums2[i]; } return max(s2 + f(nums1, nums2), s1 + f(nums2, nums1)); } int f(vector<int> &nums1, vector<int> &nums2) { int t = nums1[0] - nums2[0]; int mx = t; for (int i = 1; i < nums1.size(); ++i) { int v = nums1[i] - nums2[i]; if (t > 0) t += v; else t = v; mx = max(mx, t); } return mx; }};class Solution: def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int: def f(nums1, nums2): d = [a - b for a, b in zip(nums1, nums2)] t = mx = d[0] for v in d[1:]: if t > 0: t += v else: t = v mx = max(mx, t) return mx s1, s2 = sum(nums1), sum(nums2) return max(s2 + f(nums1, nums2), s1 + f(nums2, nums1))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.