Get the Maximum Score

Get the Maximum Score

What is this problem about?

The Get the Maximum Score coding problem gives you two sorted arrays of distinct integers. You can start traversing from either array. When you encounter an element that exists in both arrays, you are allowed to switch your path to the other array. Your score is the sum of all unique elements you visit. You must find the maximum possible score and return it modulo $10^9 + 7$.

Why is this asked in interviews?

This is a "Hard" difficulty problem asked by Google and Microsoft. It tests a candidate's ability to combine Two Pointers with Dynamic Programming / Greedy logic. It evaluates whether you can process two sequences simultaneously and recognize that "common elements" act as checkpoints where you can choose the optimal path accumulated so far.

Algorithmic pattern used

This problem is solved using a Two Pointers and Segment Sum approach.

1. Use two pointers, i for nums1 and j for nums2.
2. Maintain two running sums: sum1 and sum2.
3. Move the pointer that points to the smaller value and add that value to its respective sum.
4. If you hit a common element (nums1[i] == nums2[j]), it's a checkpoint.
5. At the checkpoint, you can choose the best path up to this point. So, add max(sum1, sum2) + common_element to the total score.
6. Reset sum1 and sum2 to 0, advance both pointers, and continue.
7. After the loop, add the remaining max sum to the total score.

Example explanation

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

1. i=0 (2), j=0 (4). 2 < 4, sum1 += 2 = 2. i++.
2. i=1 (4), j=0 (4). Match! Checkpoint at 4.
   • Max previous: max(sum1 (2), sum2 (0)) = 2.
   • Add to total: Total = 2 + 4 = 6.
   • Reset sum1=0, sum2=0. i++, j++.
3. i=2 (5), j=1 (6). 5 < 6, sum1 += 5. i++.
4. i=3 (8), j=2 (8). Match! Checkpoint at 8.
   • Max previous: max(sum1 (5), sum2 (6)) = 6.
   • Add to total: Total = 6 + 6 + 8 = 20.
   • Reset sum1=0, sum2=0. i++, j++. Result builds up optimally at every intersection.

Common mistakes candidates make

• Integer Overflow: The sums can get very large. You must use 64-bit integers (long) for sum1, sum2, and total before applying the modulo at the very end. Applying modulo during the max() comparison will ruin the logic.
• Ignoring Tails: Forgetting to add the remaining elements of the arrays after the last intersection point.
• $O(N \log N)$ Search: Using binary search to find common elements instead of the $O(N)$ two-pointer approach available for sorted arrays.

Interview preparation tip

Treat matching elements in two sorted arrays as "bridges" or "save points." You independently accumulate scores on both roads, and when you reach a bridge, you permanently bank the higher score and start fresh.