题目描述
你有两个 有序 且数组内元素互不相同的数组 nums1
和 nums2
。
一条 合法路径 定义如下:
- 选择数组
nums1
或者nums2
开始遍历(从下标 0 处开始)。 - 从左到右遍历当前数组。
- 如果你遇到了
nums1
和nums2
中都存在的值,那么你可以切换路径到另一个数组对应数字处继续遍历(但在合法路径中重复数字只会被统计一次)。
得分定义为合法路径中不同数字的和。
请你返回所有可能合法路径中的最大得分。
由于答案可能很大,请你将它对 10^9 + 7
取余后返回。
样例
输入:nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
输出:30
解释:合法路径包括:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],(从 nums1 开始遍历)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] (从 nums2 开始遍历)
最大得分为上图中的绿色路径 [2,4,6,8,10]。
输入:nums1 = [1,3,5,7,9], nums2 = [3,5,100]
输出:109
解释:最大得分由路径 [1,3,5,100] 得到。
输入:nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
输出:40
解释:nums1 和 nums2 之间无相同数字。
最大得分由路径 [6,7,8,9,10] 得到。
输入:nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
输出:61
限制
1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1
和nums2
都是严格递增的数组。
算法
(动态规划) $O(n + m)$
- 我们可以把两个数组通过相同的数字捏在一起,即相同的数字看做一个结点,此时问题的拓扑结构就很清晰了,每个数字相同的结点有两个前驱,其余都只有一个前驱。
- 这个问题可以很容易的用动态规划求解,和数字三角形类似。
- 注意此题的一个坑点是,不能在求解的过程中取余(否则会破坏最大值的定义),需要用到 64 位整型。
时间复杂度
- 分别遍历两个数组一次,故时间复杂度为 $O(n + m)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
public:
int maxSum(vector<int>& nums1, vector<int>& nums2) {
const int mod = 1000000007;
const int n = nums1.size(), m = nums2.size();
LL f = 0, g = 0;
int i = 0, j = 0;
while (i < n && j < m) {
if (nums1[i] < nums2[j]) f += nums1[i++];
else if (nums1[i] > nums2[j]) g += nums2[j++];
else {
if (f > g) {
f += nums1[i++];
g = f; j++;
} else {
g += nums2[j++];
f = g; i++;
}
}
}
while (i < n) f += nums1[i++];
while (j < m) g += nums2[j++];
if (f > g)
return f % mod;
return g % mod;
}
};
en