Get the Maximum Score

Problem Description

Given two sorted arrays of distinct integers, the goal is to construct a valid path by traversing either array from left to right and switching between them at common elements. The score is the sum of the visited elements, and you want to maximize this sum. Since the arrays are sorted, you can only move forward, and at a common element you may choose the path with the highest accumulated sum. Return the maximum score achievable modulo 10^9 + 7.

Key Insights

• Both arrays are sorted and contain distinct values.
• Use two pointers to traverse both arrays simultaneously.
• Maintain two cumulative sums (one for each array) until encountering a common element.
• At a common element, add the maximum of the two cumulative sums plus the common value and reset both running sums.
• Once one array is fully processed, add the remaining elements from the other.
• This approach is both greedy and dynamic programming oriented.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of nums1 and nums2 respectively. Space Complexity: O(1) extra space.

Solution

Use two pointers to iterate through both arrays while accumulating sums. When a common element is found:

1. Add the common element to the maximum of the two cumulative sums.
2. Set both cumulative sums to this new value.
3. Continue traversing. Finally, add the remaining values from the array that still has unprocessed elements. Return the maximum of the two cumulative totals modulo 10^9 + 7.

Code Solutions