Get the Maximum Score

• We define a recursive function, let's call it solve(index, isNums1), which calculates the maximum score starting from index in either nums1 (if isNums1 is true) or nums2.
• To avoid recomputing results for the same state (e.g., solve(5, true)), we use two memoization arrays, memo1 for nums1 and memo2 for nums2.
• Base Case: If the index goes out of bounds for the respective array, the path ends, so we return 0.
• Memoization Check: Before computing, we check if the result for the current state is already stored in our memoization table. If so, we return the stored value.
• Recursive Step for solve(i, true) (i.e., for nums1[i]):
  1. The score from this point will include nums1[i]. The default next step is to continue in nums1, so we recursively call solve(i + 1, true).
  2. We then check if nums1[i] is a common element by searching for it in nums2. A binary search is efficient for this since nums2 is sorted.
  3. If nums1[i] is found in nums2 at index j, we have a choice: either continue in nums1 or switch to nums2. We calculate the score for switching, which would be nums1[i] + solve(j + 1, false).
  4. We take the maximum of the two options (staying vs. switching).
  5. Store the computed maximum score in memo1[i] and return it.
• The logic for solve(j, false) (for nums2) is symmetrical.
• The final answer is the maximum of starting from the beginning of nums1 or nums2, i.e., max(solve(0, true), solve(0, false)). All additions should be done using long to prevent overflow, and the final result is taken modulo 10^9 + 7.

We can frame this problem recursively. The maximum score from any point i in an array is the value array[i] plus the maximum score achievable from the next steps. The next step can either be array[i+1] or, if array[i] is a common element, we can switch to the other array from the corresponding position.

This leads to overlapping subproblems. For instance, we might need to calculate the maximum score from nums1[k] multiple times through different paths. Dynamic programming with memoization is a perfect fit here.

We'll use two arrays, memo1 and memo2, to store the calculated maximum scores starting from each index of nums1 and nums2, respectively. The recursive function will first check the memoization table before performing any computation. To find if an element is common and get its index in the other array, we can use binary search, which is efficient because the arrays are sorted.

1class Solution {2    long[] memo1;3    long[] memo2;4    int MOD = 1_000_000_007;5    int[] n1, n2;6 7    public int maxSum(int[] nums1, int[] nums2) {8        this.n1 = nums1;9        this.n2 = nums2;10        memo1 = new long[nums1.length];11        memo2 = new long[nums2.length];12        java.util.Arrays.fill(memo1, -1);13        java.util.Arrays.fill(memo2, -1);14 15        // We need to find the max score starting from index 0 of either array16        long maxScore = Math.max(solve(0, true), solve(0, false));17 18        return (int) (maxScore % MOD);19    }20 21    private long solve(int index, boolean isNums1) {22        if (isNums1) {23            if (index >= n1.length) return 0;24            if (memo1[index] != -1) return memo1[index];25 26            long currentVal = n1[index];27            // Option 1: Continue in nums128            long res = currentVal + solve(index + 1, true);29 30            // Check for Option 2: Switch to nums2 if possible31            int otherIndex = java.util.Arrays.binarySearch(n2, (int)currentVal);32            if (otherIndex >= 0) {33                res = Math.max(res, currentVal + solve(otherIndex + 1, false));34            }35            return memo1[index] = res;36        } else {37            if (index >= n2.length) return 0;38            if (memo2[index] != -1) return memo2[index];39 40            long currentVal = n2[index];41            // Option 1: Continue in nums242            long res = currentVal + solve(index + 1, false);43 44            // Check for Option 2: Switch to nums1 if possible45            int otherIndex = java.util.Arrays.binarySearch(n1, (int)currentVal);46            if (otherIndex >= 0) {47                res = Math.max(res, currentVal + solve(otherIndex + 1, true));48            }49            return memo2[index] = res;50        }51    }52}

• Initialize two pointers, i for nums1 and j for nums2, both at 0.
• Initialize two long variables, sum1 and sum2, to 0. These will store the sums of the current path segments in each array.
• Initialize a long variable ans to 0, which will accumulate the final maximum score.
• Iterate with a while loop as long as both pointers i and j are within their respective array bounds.
  • Case 1: nums1[i] < nums2[j]: The element nums1[i] is not a common point. Add it to the current segment sum for nums1 (sum1 += nums1[i]) and advance the i pointer (i++).
  • Case 2: nums2[j] < nums1[i]: Similarly, add nums2[j] to sum2 and advance the j pointer.
  • Case 3: nums1[i] == nums2[j]: A common element is found. This is a point where we can switch paths. To maximize the score, we choose the segment with the larger sum (Math.max(sum1, sum2)), add it to our total answer ans, and also add the value of the common element itself. After this, we reset sum1 and sum2 to 0 for the next segments and advance both pointers i and j.
• After the loop, one of the arrays might still have unvisited elements. These form the final segment of a possible path. We iterate through the remainder of nums1 (if any) adding to sum1, and the remainder of nums2 (if any) adding to sum2.
• Finally, we add the larger of these two final segment sums (Math.max(sum1, sum2)) to our total answer ans.
• Return ans modulo 10^9 + 7.

The core idea is to break down the problem into segments. A segment is a sequence of numbers in one array between two consecutive common elements. At every common element, we have the choice to switch from one array to the other. The greedy strategy is that to maximize the total sum, at each such junction, we should always come from the path that has accumulated a larger sum so far.

We can implement this efficiently using two pointers, one for each array. We advance the pointers, summing up elements for each array's current segment. When the pointers meet at a common value, we compare the segment sums, add the larger one to our total score, add the common value itself, and then reset the segment sums to start fresh for the next part of the journey.

1class Solution {2    public int maxSum(int[] nums1, int[] nums2) {3        int n = nums1.length;4        int m = nums2.length;5        long sum1 = 0;6        long sum2 = 0;7        long ans = 0;8        int i = 0;9        int j = 0;10        int MOD = 1_000_000_007;11 12        while (i < n && j < m) {13            if (nums1[i] < nums2[j]) {14                sum1 += nums1[i];15                i++;16            } else if (nums2[j] < nums1[i]) {17                sum2 += nums2[j];18                j++;19            } else { // Common element found20                // Choose the path with the maximum sum so far21                ans += Math.max(sum1, sum2) + nums1[i];22                // Reset sums for the next segment23                sum1 = 0;24                sum2 = 0;25                i++;26                j++;27            }28        }29 30        // Add remaining elements from nums1, if any31        while (i < n) {32            sum1 += nums1[i];33            i++;34        }35 36        // Add remaining elements from nums2, if any37        while (j < m) {38            sum2 += nums2[j];39            j++;40        }41 42        // Add the maximum of the last segment sums43        ans += Math.max(sum1, sum2);44 45        return (int) (ans % MOD);46    }47}