Get the Maximum Score
You are given two sorted arrays of distinct integers nums1 and nums2.
A valid path is defined as follows:
- Choose array
nums1ornums2to traverse from index0. - Traverse the current array from left to right.
- If you are reading any value that is present in both
nums1andnums2, you are allowed to change your path to the other array. Only one repeated value is considered in the valid path.
The score is defined as the sum of unique values in a valid path.
Return the maximum score you can obtain among all possible valid paths. Since the answer may be too large, return it modulo 10^9 + 7.
Example 1
Input
nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]Output
30Among all valid paths, the maximum score is obtained by the path [2, 4, 6, 8, 10], whose sum is 30.
Example 2
Input
nums1 = [1,3,5,7,9], nums2 = [3,5,100]Output
109Maximum sum is obtained with the path [1, 3, 5, 100].
Constraints
- 1 <= nums1.length, nums2.length <= 10^5
- 1 <= nums1[i], nums2[i] <= 10^7
- nums1 and nums2 are strictly increasing.