你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。
一条 合法路径 定义如下:
得分定义为合法路径中不同数字的和。
请你返回所有可能合法路径中的最大得分。
由于答案可能很大,请你将它对 10^9 + 7 取余后返回。
示例 1:
输入: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] 。
示例 2:
输入:nums1 = [1,3,5,7,9], nums2 = [3,5,100]
输出:109
解释:最大得分由路径 [1,3,5,100] 得到。
示例 3:
输入:nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
输出:40
解释:nums1 和 nums2 之间无相同数字。
最大得分由路径 [6,7,8,9,10] 得到。
示例 4:
输入: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 都是严格递增的数组。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/get-the-maximum-score 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int maxSum(vector<int>& nums1, vector<int>& nums2) {
long long ans = 0, up_sum = 0, down_sum = 0;
int i = 0, j = 0, n1 = nums1.size(), n2 = nums2.size();
while(i < n1 && j < n2)
{
if(nums1[i] < nums2[j])
{
up_sum += nums1[i++];
}
else if(nums1[i] > nums2[j])
{
down_sum += nums2[j++];
}
else if(nums1[i] == nums2[j])
{
up_sum += nums1[i++];
down_sum += nums2[j++];
//相同的点,取前面较大的片段之和
ans = (ans+max(up_sum, down_sum))%1000000007;
up_sum = down_sum = 0;//片段和置0
}
}
while(i < n1)//剩余的没遍历完的
up_sum += nums1[i++];
while(j < n2)
down_sum += nums2[j++];
ans = (ans+max(up_sum, down_sum))%1000000007;
return ans;
}
};
236 ms 55.7 MB