Description#
You are given two sorted arrays of distinct integers nums1
and nums2
.
A valid path is defined as follows:
- Choose array
nums1
or nums2
to traverse (from index-0). - Traverse the current array from left to right.
- If you are reading any value that is present in
nums1
and nums2
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 of all possible valid paths. Since the answer may be too large, return it modulo 109 + 7
.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/1537.Get%20the%20Maximum%20Score/images/sample_1_1893.png)
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].
Constraints:
1 <= nums1.length, nums2.length <= 105
1 <= nums1[i], nums2[i] <= 107
nums1
and nums2
are strictly increasing.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
mod = 10**9 + 7
m, n = len(nums1), len(nums2)
i = j = 0
f = g = 0
while i < m or j < n:
if i == m:
g += nums2[j]
j += 1
elif j == n:
f += nums1[i]
i += 1
elif nums1[i] < nums2[j]:
f += nums1[i]
i += 1
elif nums1[i] > nums2[j]:
g += nums2[j]
j += 1
else:
f = g = max(f, g) + nums1[i]
i += 1
j += 1
return max(f, g) % mod
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int maxSum(int[] nums1, int[] nums2) {
final int mod = (int) 1e9 + 7;
int m = nums1.length, n = nums2.length;
int i = 0, j = 0;
long f = 0, g = 0;
while (i < m || j < n) {
if (i == m) {
g += nums2[j++];
} else if (j == n) {
f += nums1[i++];
} else if (nums1[i] < nums2[j]) {
f += nums1[i++];
} else if (nums1[i] > nums2[j]) {
g += nums2[j++];
} else {
f = g = Math.max(f, g) + nums1[i];
i++;
j++;
}
}
return (int) (Math.max(f, g) % mod);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int maxSum(vector<int>& nums1, vector<int>& nums2) {
const int mod = 1e9 + 7;
int m = nums1.size(), n = nums2.size();
int i = 0, j = 0;
long long f = 0, g = 0;
while (i < m || j < n) {
if (i == m) {
g += nums2[j++];
} else if (j == n) {
f += nums1[i++];
} else if (nums1[i] < nums2[j]) {
f += nums1[i++];
} else if (nums1[i] > nums2[j]) {
g += nums2[j++];
} else {
f = g = max(f, g) + nums1[i];
i++;
j++;
}
}
return max(f, g) % mod;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func maxSum(nums1 []int, nums2 []int) int {
const mod int = 1e9 + 7
m, n := len(nums1), len(nums2)
i, j := 0, 0
f, g := 0, 0
for i < m || j < n {
if i == m {
g += nums2[j]
j++
} else if j == n {
f += nums1[i]
i++
} else if nums1[i] < nums2[j] {
f += nums1[i]
i++
} else if nums1[i] > nums2[j] {
g += nums2[j]
j++
} else {
f = max(f, g) + nums1[i]
g = f
i++
j++
}
}
return max(f, g) % mod
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| function maxSum(nums1: number[], nums2: number[]): number {
const mod = 1e9 + 7;
const m = nums1.length;
const n = nums2.length;
let [f, g] = [0, 0];
let [i, j] = [0, 0];
while (i < m || j < n) {
if (i === m) {
g += nums2[j++];
} else if (j === n) {
f += nums1[i++];
} else if (nums1[i] < nums2[j]) {
f += nums1[i++];
} else if (nums1[i] > nums2[j]) {
g += nums2[j++];
} else {
f = g = Math.max(f, g) + nums1[i];
i++;
j++;
}
}
return Math.max(f, g) % mod;
}
|