Problem Description

You are given two sorted arrays of positive integers, nums1 and nums2. You start with either array and traverse from left to right, moving one step at a time. At any index where the two arrays have the same value, you are allowed to switch from one array to the other. The goal is to maximize the sum of the values collected as you traverse, and you can only visit each index once (i.e., do not reuse elements). Return the maximum possible sum modulo 10^9 + 7.

• Each element can be used at most once.
• At each matching value (intersection), you may switch between arrays.
• Arrays are sorted and may have different lengths.
• Only one valid solution is required.

Thought Process

At first glance, it seems like you could try every possible path, switching at every intersection. But with many intersections, the number of possible paths grows very quickly—making brute-force approaches infeasible.

The core insight is that, between intersections (matching values), you can only move forward in a given array, and you can only switch at matches. So, for each segment between matches, you want to collect the maximum sum possible from either array. At each intersection, you can choose the best path so far, add the intersection value, and continue.

This leads us to a two-pointer approach, where we traverse both arrays simultaneously, keeping track of the maximum sum we've accumulated in each array up to the current point.

Solution Approach

Let's break down the solution step-by-step:

1. Initialize Two Pointers and Sums:
   • Set pointers i and j at the start of nums1 and nums2, respectively.
   • Initialize sum1 and sum2 to keep track of the running totals in each array.
2. Traverse Both Arrays:
   • While both pointers are within bounds, compare nums1[i] and nums2[j].
   • If nums1[i] < nums2[j], add nums1[i] to sum1 and increment i.
   • If nums2[j] < nums1[i], add nums2[j] to sum2 and increment j.
   • If nums1[i] == nums2[j] (intersection):
   • Add the maximum of sum1 and sum2 plus the intersection value to both sums.
   • Reset both sums to this new value and increment both pointers.
3. Process Remaining Elements:
   • After one array is exhausted, continue adding remaining elements of the other array to its respective sum.
4. Return the Answer:
   • The result is the maximum of sum1 and sum2, modulo 10^9 + 7.

This approach guarantees we always take the optimal path at each intersection and efficiently computes the answer in linear time.

Example Walkthrough

Let's use the following example:

    nums1 = [2, 4, 5, 8, 10]
    nums2 = [4, 6, 8, 9]
  

1. Start: i=0, j=0, sum1=0, sum2=0
2. nums1[0]=2 < nums2[0]=4; add 2 to sum1 → sum1=2, i=1
3. nums1[1]=4 == nums2[0]=4; intersection!
   • max(sum1, sum2) + 4 = max(2,0) + 4 = 6
   • sum1 = sum2 = 6, i=2, j=1
4. nums1[2]=5 < nums2[1]=6; add 5 to sum1 → sum1=11, i=3
5. nums1[3]=8 > nums2[1]=6; add 6 to sum2 → sum2=12, j=2
6. nums1[3]=8 == nums2[2]=8; intersection!
   • max(sum1, sum2) + 8 = max(11,12) + 8 = 20
   • sum1 = sum2 = 20, i=4, j=3
7. nums1[4]=10 > nums2[3]=9; add 9 to sum2 → sum2=29, j=4
8. nums2 exhausted; add remaining nums1[4]=10 to sum1 → sum1=30, i=5
9. Result: max(sum1,sum2) = max(30,29) = 30

So, the maximum score is 30.

Time and Space Complexity

• Brute-force approach:
  • Try all possible paths, switching at every intersection. The number of possible paths is exponential in the number of intersections, so time complexity is O(2^k) where k is the number of intersections. This is infeasible for large inputs.
• Optimized two-pointer approach:
  • Each element from both arrays is visited once, so time complexity is O(n + m), where n and m are the lengths of nums1 and nums2.
  • Space complexity is O(1) (ignoring input), as only a few variables are used.

Summary

The key to solving the "Get the Maximum Score" problem is recognizing that, between intersections, you should always take the path with the greater accumulated sum. By using a two-pointer approach and updating your running totals at each intersection, you efficiently compute the optimal answer in linear time. This method elegantly sidesteps the exponential complexity of brute-force search, making it both efficient and easy to implement.

Code Implementation

class Solution:
    def maxSum(self, nums1, nums2):
        MOD = 10 ** 9 + 7
        i, j = 0, 0
        sum1, sum2 = 0, 0
        n, m = len(nums1), len(nums2)
        while i < n and j < m:
            if nums1[i] < nums2[j]:
                sum1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                sum2 += nums2[j]
                j += 1
            else:
                max_sum = max(sum1, sum2) + nums1[i]
                sum1 = sum2 = max_sum
                i += 1
                j += 1
        while i < n:
            sum1 += nums1[i]
            i += 1
        while j < m:
            sum2 += nums2[j]
            j += 1
        return max(sum1, sum2) % MOD
      

class Solution {
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        const int MOD = 1e9 + 7;
        int n = nums1.size(), m = nums2.size();
        int i = 0, j = 0;
        long sum1 = 0, sum2 = 0;
        while (i < n && j < m) {
            if (nums1[i] < nums2[j]) {
                sum1 += nums1[i++];
            } else if (nums1[i] > nums2[j]) {
                sum2 += nums2[j++];
            } else {
                long max_sum = max(sum1, sum2) + nums1[i];
                sum1 = sum2 = max_sum;
                ++i; ++j;
            }
        }
        while (i < n) sum1 += nums1[i++];
        while (j < m) sum2 += nums2[j++];
        return (int)(max(sum1, sum2) % MOD);
    }
};
      

class Solution {
    public int maxSum(int[] nums1, int[] nums2) {
        final int MOD = 1_000_000_007;
        int n = nums1.length, m = nums2.length;
        int i = 0, j = 0;
        long sum1 = 0, sum2 = 0;
        while (i < n && j < m) {
            if (nums1[i] < nums2[j]) {
                sum1 += nums1[i++];
            } else if (nums1[i] > nums2[j]) {
                sum2 += nums2[j++];
            } else {
                long maxSum = Math.max(sum1, sum2) + nums1[i];
                sum1 = sum2 = maxSum;
                i++; j++;
            }
        }
        while (i < n) sum1 += nums1[i++];
        while (j < m) sum2 += nums2[j++];
        return (int)(Math.max(sum1, sum2) % MOD);
    }
}
      

var maxSum = function(nums1, nums2) {
    const MOD = 1e9 + 7;
    let i = 0, j = 0;
    let sum1 = 0, sum2 = 0;
    const n = nums1.length, m = nums2.length;
    while (i < n && j < m) {
        if (nums1[i] < nums2[j]) {
            sum1 += nums1[i++];
        } else if (nums1[i] > nums2[j]) {
            sum2 += nums2[j++];
        } else {
            let maxSum = Math.max(sum1, sum2) + nums1[i];
            sum1 = sum2 = maxSum;
            i++; j++;
        }
    }
    while (i < n) sum1 += nums1[i++];
    while (j < m) sum2 += nums2[j++];
    return Math.max(sum1, sum2) % MOD;
};