Maximum Score Of Spliced Array — Problem & Solution
Maximum Score Of Spliced Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Score Of Spliced Array is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two arrays nums1 and nums2 of the same length n. You may choose indices left <= right and swap the subarrays nums1[left..right] and nums2[left..right], or choose not to swap anything at all (at most one swap).
The score is max(sum(nums1), sum(nums2)) after the optional swap. Return the maximum possible score.
Example 1
Input: nums1 = [1,9,1], nums2 = [8,2,8]
Output: 25
Explanation: Swap index 1 only: `nums2` becomes `[8,9,8]` with sum 25.
Example 2
Input: nums1 = [5,5,5], nums2 = [1,1,1]
Output: 15
Explanation: No swap is best.
Example 3
Input: nums1 = [3,8,2,6], nums2 = [7,1,9,4]
Output: 28
Constraints
n == nums1.length == nums2.length1 <= n <= 10^51 <= nums1[i], nums2[i] <= 10^4
Hints for Maximum Score Of Spliced Array
Hint 1
Try to maximise each array's sum separately; the score is the larger of the two results.
Hint 2
Swapping
[l..r]changessum(nums1)bysum(nums2[l..r]) - sum(nums1[l..r]).Hint 3
So the best gain for
nums1is the maximum subarray sum ofnums2[i] - nums1[i](or 0) — Kadane's algorithm. Do the same with the roles reversed.
How to solve Maximum Score Of Spliced Array
The gain from splicing [l..r] into nums1 is the sum of nums2[i] - nums1[i] over that range, so the best splice for nums1 is a maximum-subarray problem. Solve it for both directions with Kadane's algorithm.
Approach
- Compute
s1 = sum(nums1)ands2 = sum(nums2). - Run Kadane on
d[i] = nums2[i] - nums1[i], allowing the empty range (gain 0):cur = max(0, cur + d[i]),g1 = max(g1, cur). - Run it again on
nums1[i] - nums2[i]to getg2. - Return
max(s1 + g1, s2 + g2).
Why it works
After swapping [l..r], nums1's sum is s1 + sum(d[l..r]) and nums2's is s2 - sum(d[l..r]). Maximising the larger of the two is the same as maximising each one on its own and taking the better, and each is a maximum subarray sum over a fixed array — exactly what Kadane computes in one pass.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Score the array that gains, not the one that loses — run Kadane in both directions.
- Allow a gain of 0 (no swap) so an all-negative difference array does not lower the answer.
- Sums reach
10^9; that fits in 32 bits, but 64-bit accumulation is the safe habit.
Reference solution
Python
from typing import List
def maximumsSplicedArray(nums1: List[int], nums2: List[int]) -> int:
def gain(a, b):
best = cur = 0
for x, y in zip(a, b):
cur = max(0, cur + y - x)
best = max(best, cur)
return best
return max(sum(nums1) + gain(nums1, nums2), sum(nums2) + gain(nums2, nums1))Java
private static long gainSA(int[] a, int[] b) {
long best = 0, cur = 0;
for (int i = 0; i < a.length; i++) {
cur = Math.max(0, cur + b[i] - a[i]);
best = Math.max(best, cur);
}
return best;
}
public static int maximumsSplicedArray(int[] nums1, int[] nums2) {
long s1 = 0, s2 = 0;
for (int i = 0; i < nums1.length; i++) { s1 += nums1[i]; s2 += nums2[i]; }
return (int) Math.max(s1 + gainSA(nums1, nums2), s2 + gainSA(nums2, nums1));
}C++
static long long gainSA(const vector<int>& a, const vector<int>& b) {
long long best = 0, cur = 0;
for (size_t i = 0; i < a.size(); i++) {
cur = max(0LL, cur + b[i] - a[i]);
best = max(best, cur);
}
return best;
}
int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
long long s1 = 0, s2 = 0;
for (size_t i = 0; i < nums1.size(); i++) { s1 += nums1[i]; s2 += nums2[i]; }
return (int)max(s1 + gainSA(nums1, nums2), s2 + gainSA(nums2, nums1));
}JavaScript
var maximumsSplicedArray = function(nums1, nums2) {
var gain = function(a, b) {
var best = 0, cur = 0;
for (var i = 0; i < a.length; i++) {
cur = Math.max(0, cur + b[i] - a[i]);
if (cur > best) best = cur;
}
return best;
};
var s1 = 0, s2 = 0;
for (var i = 0; i < nums1.length; i++) { s1 += nums1[i]; s2 += nums2[i]; }
return Math.max(s1 + gain(nums1, nums2), s2 + gain(nums2, nums1));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming