Code Implementation

class Solution:
    def maximumsSplicedArray(self, nums1, nums2):
        def max_gain(arr1, arr2):
            # Find the max subarray sum of (arr2[i] - arr1[i])
            max_diff = cur = 0
            for a, b in zip(arr1, arr2):
                cur = max(b - a, cur + b - a)
                max_diff = max(max_diff, cur)
            return max_diff
        
        sum1 = sum(nums1)
        sum2 = sum(nums2)
        gain1 = max_gain(nums1, nums2)
        gain2 = max_gain(nums2, nums1)
        return max(sum1 + gain1, sum2 + gain2)
      

class Solution {
public:
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        auto max_gain = [](const vector<int>& arr1, const vector<int>& arr2) {
            int max_diff = 0, cur = 0;
            for (size_t i = 0; i < arr1.size(); ++i) {
                cur = max(arr2[i] - arr1[i], cur + arr2[i] - arr1[i]);
                max_diff = max(max_diff, cur);
            }
            return max_diff;
        };
        int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
        int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
        int gain1 = max_gain(nums1, nums2);
        int gain2 = max_gain(nums2, nums1);
        return max(sum1 + gain1, sum2 + gain2);
    }
};
      

class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        int sum1 = 0, sum2 = 0;
        for (int x : nums1) sum1 += x;
        for (int x : nums2) sum2 += x;
        int gain1 = maxGain(nums1, nums2);
        int gain2 = maxGain(nums2, nums1);
        return Math.max(sum1 + gain1, sum2 + gain2);
    }
    
    private int maxGain(int[] arr1, int[] arr2) {
        int maxDiff = 0, cur = 0;
        for (int i = 0; i < arr1.length; ++i) {
            cur = Math.max(arr2[i] - arr1[i], cur + arr2[i] - arr1[i]);
            maxDiff = Math.max(maxDiff, cur);
        }
        return maxDiff;
    }
}
      

var maximumsSplicedArray = function(nums1, nums2) {
    function maxGain(arr1, arr2) {
        let maxDiff = 0, cur = 0;
        for (let i = 0; i < arr1.length; ++i) {
            cur = Math.max(arr2[i] - arr1[i], cur + arr2[i] - arr1[i]);
            maxDiff = Math.max(maxDiff, cur);
        }
        return maxDiff;
    }
    let sum1 = nums1.reduce((a, b) => a + b, 0);
    let sum2 = nums2.reduce((a, b) => a + b, 0);
    let gain1 = maxGain(nums1, nums2);
    let gain2 = maxGain(nums2, nums1);
    return Math.max(sum1 + gain1, sum2 + gain2);
};
      

Problem Description

• Only one subarray swap is allowed (or none).
• The swapped subarray must be contiguous and can be of any length (including the entire array).
• You can choose to swap to maximize nums1 or nums2.
• Input arrays have the same length.

Thought Process

Solution Approach

1. Calculate the initial sums:
   • Find the sum of nums1 and nums2 as they are.
2. Find the best subarray to swap:
   • For maximizing nums1, compute the difference array diff[i] = nums2[i] - nums1[i].
   • The subarray swap that gives the maximum gain is the subarray with the largest sum in diff (Kadane's algorithm).
   • Similarly, for maximizing nums2, compute diff[i] = nums1[i] - nums2[i] and find its maximum subarray sum.
3. Apply the best swap:
   • The maximum possible sum is the higher of:
     • sum(nums1) + max_gain_for_nums1
     • sum(nums2) + max_gain_for_nums2

This approach uses Kadane's algorithm to find the maximum subarray sum, which is efficient and avoids brute-forcing all possible swaps.

Example Walkthrough

Suppose nums1 = [60, 60, 60] and nums2 = [10, 90, 10].

1. Initial sums:
   sum1 = 180, sum2 = 110
2. For maximizing nums1:
   • Compute diff = [10-60, 90-60, 10-60] = [-50, 30, -50]
   • Maximum subarray sum in diff is 30 (just the middle element).
   • So, max_sum1 = 180 + 30 = 210
3. For maximizing nums2:
   • Compute diff = [60-10, 60-90, 60-10] = [50, -30, 50]
   • Maximum subarray sum is 50 + -30 + 50 = 70 (whole array).
   • So, max_sum2 = 110 + 70 = 180
4. Final answer:
   The maximum possible sum after at most one swap is 210.

In this example, swapping the second element gives nums1 = [60, 90, 60], sum = 210.

Time and Space Complexity

• Brute-force approach:
  • Try every possible subarray (O(n²)), swap, and compute sums (O(n)), for a total O(n³) time.
  • This is too slow for large arrays.
• Optimized approach (Kadane's algorithm):
  • Calculating the difference array: O(n)
  • Kadane's algorithm to find the max subarray sum: O(n)
  • Final sum calculations: O(n)
  • Total time: O(n)
  • Space: O(1) extra (if done in-place), or O(n) if storing the difference array explicitly.

Summary

In summary, the problem is elegantly solved by reducing it to a maximum subarray sum problem on the difference array. This insight allows us to use Kadane's algorithm for an efficient O(n) solution. By considering both arrays and choosing the best possible gain from a single subarray swap, we maximize the sum in either array. The key takeaway is the transformation from a brute-force mindset to leveraging well-known algorithms for optimal performance.