Maximum Score Of Spliced Array - Practice Coding Problems

Maximum Score Of Spliced 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.

Input & Output

Example 1 — Basic Swap

$ Input: nums1 = [60,60,60], nums2 = [10,90,10]

› Output: 210

💡 Note: Swap index 1: nums1 becomes [60,90,60] with sum 210, nums2 becomes [10,60,10] with sum 80. Maximum is 210.

Example 2 — No Swap Better

$ Input: nums1 = [20,40,20,70,30], nums2 = [50,20,50,40,20]

› Output: 220

💡 Note: Original sums are 180 and 180. Best swap gives nums1=[20,20,50,40,30] (sum=160) or nums2=[50,40,20,70,20] (sum=200). But swapping [1,3] gives nums2=[50,40,50,70,20] with sum=230, but nums1=[20,20,20,40,30] has sum=130. Maximum is 230, but optimal is actually swapping nums1[3,4]→nums2[3,4] giving nums1=[20,40,20,40,20] (sum=140) and nums2=[50,20,50,70,30] (sum=220). Maximum is 220.

Example 3 — Single Element

$ Input: nums1 = [100], nums2 = [50]

› Output: 100

💡 Note: Can swap to get nums1=[50], nums2=[100], but original nums1 sum of 100 is already maximum.

Constraints

1 ≤ nums1.length, nums2.length ≤ 10⁵
nums1.length == nums2.length
-10⁴ ≤ nums1[i], nums2[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays with same length

Process

Find optimal subarray to swap

Output

Maximum possible array sum

Key Takeaway

🎯 Key Insight: Use Kadane's algorithm on difference arrays to find optimal swap in O(n) time

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use Kadane's algorithm on the difference array to find the optimal subarray to swap. Instead of trying all O(n²) possible swaps, we calculate the benefit of each position swap and find the maximum subarray benefit in O(n) time. Best approach uses Kadane's algorithm: Time O(n), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Swaps	O(n³)	O(1)	Try every possible subarray swap and calculate the maximum score
Kadane's Algorithm - Optimal Solution	O(n)	O(1)	Use modified Kadane's algorithm on the difference array to find optimal swap

Brute Force - Try All Swaps — Algorithm Steps

Try all possible left and right boundaries
For each pair, swap subarrays and calculate sums
Track the maximum score from all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Arrays

Start with nums1 and nums2

Try All Swaps

Test every left,right boundary pair

Maximum Score

Return the highest score found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums1, int* nums2, int n) {
    // Calculate initial sums
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < n; i++) {
        sum1 += nums1[i];
        sum2 += nums2[i];
    }
    int maxScore = sum1 > sum2 ? sum1 : sum2;
    
    // Try all possible swaps
    for (int left = 0; left < n; left++) {
        for (int right = left; right < n; right++) {
            // Create copies and swap subarray
            int* newNums1 = (int*)malloc(n * sizeof(int));
            int* newNums2 = (int*)malloc(n * sizeof(int));
            memcpy(newNums1, nums1, n * sizeof(int));
            memcpy(newNums2, nums2, n * sizeof(int));
            
            for (int i = left; i <= right; i++) {
                int temp = newNums1[i];
                newNums1[i] = newNums2[i];
                newNums2[i] = temp;
            }
            
            // Calculate new sums and update max score
            int newSum1 = 0, newSum2 = 0;
            for (int i = 0; i < n; i++) {
                newSum1 += newNums1[i];
                newSum2 += newNums2[i];
            }
            int score = newSum1 > newSum2 ? newSum1 : newSum2;
            maxScore = score > maxScore ? score : maxScore;
            
            free(newNums1);
            free(newNums2);
        }
    }
    
    return maxScore;
}

int main() {
    char line[10000];
    int nums1[1000], nums2[1000];
    int n1 = 0, n2 = 0;
    
    // Parse nums1
    fgets(line, sizeof(line), stdin);
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums1[n1++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse nums2
    fgets(line, sizeof(line), stdin);
    ptr = strchr(line, '[') + 1;
    token = strtok(ptr, ",]");
    while (token != NULL) {
        nums2[n2++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums1, nums2, n1));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops for left/right boundaries (O(n²)) and sum calculation for each swap (O(n))

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track maximum score and current sums

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

423 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Swaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler