#1537
Get the Maximum Score
master · 1680 · lc hard +32 · verified · 40.9% accepted · 1,069 likes · top 21%
Description
Given two sorted arrays of distinct integers nums1 and nums2, a valid path starts in either array and traverses left-to-right. Whenever the current value appears in both arrays you may switch arrays (using that value only once). The path score is the sum of all unique values visited. Return the maximum achievable score, modulo 109 + 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: 109
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].
Code
1
2
3