# Maximum Score Of Spliced Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-score-of-spliced-array)
Canonical: https://scaleengineer.com/dsa/problems/maximum-score-of-spliced-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute Force with Triple Loop
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.
**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.
**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).
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Calculate the initial sums of `nums1` and `nums2`, let them be `sum1` and `sum2`.
2. Initialize `maxScore` with `max(sum1, sum2)`. This handles the case of not performing any swap.
3. Use a nested loop to iterate through all possible start (`left`) and end (`right`) indices of a subarray, where `0 <= left <= right < n`.
4. For each `(left, right)` pair, use a third loop to calculate the sum of the subarray `nums1[left...right]` (`sub1Sum`) and `nums2[left...right]` (`sub2Sum`).
5. Calculate the new sums of the arrays after the hypothetical swap:
   - `newSum1 = sum1 - sub1Sum + sub2Sum`
   - `newSum2 = sum2 - sub2Sum + sub1Sum`
6. Update `maxScore` by taking the maximum of its current value, `newSum1`, and `newSum2`.
7. After checking all possible subarrays, return `maxScore`.

## Optimized Brute Force with Double Loop
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.
**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.
**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'.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Calculate the initial sums of `nums1` and `nums2`, let them be `sum1` and `sum2`.
2. Initialize `maxScore` with `max(sum1, sum2)`.
3. Use an outer loop to iterate through all possible start indices (`left`) from `0` to `n-1`.
4. Inside the outer loop, initialize running sums for the current subarray, `sub1Sum = 0` and `sub2Sum = 0`.
5. Use an inner loop to iterate through all possible end indices (`right`) from `left` to `n-1`.
6. In the inner loop, update the running sums by adding the current elements: `sub1Sum += nums1[right]` and `sub2Sum += nums2[right]`.
7. Calculate the new total sums `newSum1` and `newSum2` using the running subarray sums.
8. Update `maxScore` with the maximum of its current value, `newSum1`, and `newSum2`.
9. Return `maxScore` after the loops complete.

## Linear Time Solution using Kadane's Algorithm
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.
**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.
**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.
### Explanation
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.

```java
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);
    }
}
```
### Algorithm
1. The problem can be split into two subproblems: maximizing the sum of `nums1` and maximizing the sum of `nums2`.
2. To maximize `sum(nums1)`, we need to find a subarray `[l..r]` that maximizes the gain from the swap. The new sum is `sum(nums1) + sum(nums2[l..r]) - sum(nums1[l..r])`. This is equivalent to `sum(nums1) + sum(diff[l..r])` where `diff[i] = nums2[i] - nums1[i]`. So, we need to find the maximum subarray sum of this difference array.
3. Similarly, to maximize `sum(nums2)`, we need to find the maximum subarray sum of the difference array `diff[i] = nums1[i] - nums2[i]`.
4. Both maximum subarray sum problems can be solved using Kadane's algorithm in linear time.
5. The algorithm proceeds as follows:
   a. Calculate the initial sums `sum1` and `sum2`.
   b. Apply Kadane's algorithm to find the maximum gain for `nums1` (from `nums2[i] - nums1[i]`). Add this gain to `sum1` to get a potential maximum score.
   c. Apply Kadane's algorithm to find the maximum gain for `nums2` (from `nums1[i] - nums2[i]`). Add this gain to `sum2` to get another potential maximum score.
   d. The final answer is the maximum of these two potential scores.
6. Kadane's algorithm: Initialize `maxGain = 0` and `currentGain = 0`. Iterate through the array, adding the current element's difference to `currentGain`. Update `maxGain` with `max(maxGain, currentGain)`. If `currentGain` becomes negative, reset it to 0.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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))

```