Maximum Score Of Spliced Array

Hard
1473.

Maximum Score Of Spliced Array

Maximum Score Of Spliced Array is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

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.length
  • 1 <= n <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maximumsSplicedArray = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Maximum Score Of Spliced Array

  1. Hint 1

    Try to maximise each array's sum separately; the score is the larger of the two results.

  2. Hint 2

    Swapping [l..r] changes sum(nums1) by sum(nums2[l..r]) - sum(nums1[l..r]).

  3. Hint 3

    So the best gain for nums1 is the maximum subarray sum of nums2[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

  1. Compute s1 = sum(nums1) and s2 = sum(nums2).
  2. 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).
  3. Run it again on nums1[i] - nums2[i] to get g2.
  4. 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