Get the Maximum Score

hard dp two pointers greedy

Problem

You are given two sorted arrays of distinct integers nums1 and nums2. A valid path starts at the beginning of either array and moves right; whenever the current value also appears in the other array, you may switch to it. The score of a path is the sum of its unique visited values. Return the maximum score of any valid path, modulo 10^9 + 7.

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

Output30

Best path: 2 → 4 → 6 → 8 → 10 = 30. At each shared value we add the larger of the two segment sums leading up to it.

nums1 (sorted, distinct)

nums2 (sorted, distinct)

def max_sum(nums1, nums2):
    MOD = 10**9 + 7
    i = j = 0
    sum1 = sum2 = 0
    total = 0
    while i < len(nums1) or j < len(nums2):
        if j == len(nums2) or (i < len(nums1) and nums1[i] < nums2[j]):
            sum1 += nums1[i]
            i += 1
        elif i == len(nums1) or nums2[j] < nums1[i]:
            sum2 += nums2[j]
            j += 1
        else:  # nums1[i] == nums2[j]: shared value
            total += max(sum1, sum2) + nums1[i]
            sum1 = sum2 = 0
            i += 1
            j += 1
    total += max(sum1, sum2)
    return total % MOD

function maxSum(nums1, nums2) {
  const MOD = 1000000007n;
  let i = 0, j = 0;
  let sum1 = 0n, sum2 = 0n, total = 0n;
  while (i < nums1.length || j < nums2.length) {
    if (j === nums2.length || (i < nums1.length && nums1[i] < nums2[j])) {
      sum1 += BigInt(nums1[i++]);
    } else if (i === nums1.length || nums2[j] < nums1[i]) {
      sum2 += BigInt(nums2[j++]);
    } else { // shared value
      total += (sum1 > sum2 ? sum1 : sum2) + BigInt(nums1[i]);
      sum1 = 0n; sum2 = 0n;
      i++; j++;
    }
  }
  total += sum1 > sum2 ? sum1 : sum2;
  return Number(total % MOD);
}

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

int maxSum(vector<int>& nums1, vector<int>& nums2) {
    const long MOD = 1000000007L;
    int i = 0, j = 0;
    long sum1 = 0, sum2 = 0, total = 0;
    while (i < (int)nums1.size() || j < (int)nums2.size()) {
        if (j == (int)nums2.size() || (i < (int)nums1.size() && nums1[i] < nums2[j])) {
            sum1 += nums1[i++];
        } else if (i == (int)nums1.size() || nums2[j] < nums1[i]) {
            sum2 += nums2[j++];
        } else {
            total += max(sum1, sum2) + nums1[i];
            sum1 = 0; sum2 = 0;
            i++; j++;
        }
    }
    total += max(sum1, sum2);
    return (int)(total % MOD);
}

Explanation

Both arrays are sorted, and the only places a path can jump between them are the shared values. Those common elements split each array into matching segments. Between two consecutive shared values you are locked into one array, so you simply collect that array's segment sum.

That means the decision is per segment: at each shared value, the path could have arrived via either array's preceding segment, so we take the larger of the two segment sums and then add the shared value once. This is the dynamic-programming choice — "best score to reach this junction".

We implement it with two pointers i and j sweeping the arrays together. We always advance the pointer at the smaller value, accumulating sum1 or sum2 for the current segment. When both pointers land on an equal value, we have hit a junction: add max(sum1, sum2) + sharedValue to the total and reset both running sums.

After the loop, one last segment remains beyond the final junction; we add the larger of its two tails. The grand total is taken modulo 10^9 + 7. The whole thing is a single linear pass.

Example: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]. Junctions are 4 and 8. Before 4: max(2, 0)=2. Between 4 and 8: nums1 has 5 (=5) vs nums2 has 6 (=6) → 6. After 8: nums1 has 10 (=10) vs nums2 has 9 (=9) → 10. Total = 2 + 4 + 6 + 8 + 10 = 30.

Time: O(m + n) Space: O(1)