Get the Maximum Score
You are given two sorted arrays of distinct integers nums1 and nums2.
You are given two sorted arrays of distinct integers nums1 and nums2.
A valid path is defined as follows:
The score is defined as the sum of unique values in a valid path.
Return the maximum score you can obtain of 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: 30
Explanation: Valid paths: [2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10], (starting from nums1) [4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] (starting from nums2) The maximum is obtained with the path in green [2,4,6,8,10].
Example 2
Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 10^9
Explanation: Maximum sum is obtained with the path [1,3,5,100].
Example 3
Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2. Maximum sum is obtained with the path [6,7,8,9,10].
Constraints
- 1 <= nums1.length, nums2.length <= 10^5
- 1 <= nums1[i], nums2[i] <= 10^7
- nums1 and nums2 are strictly increasing.
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.