题目大意：
最大得分
你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。
一条 合法路径 定义如下：
选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
从左到右遍历当前数组。
如果你遇到了 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1537
解题思路分析：
找到数组中相同的数字，然后将所有相同数字连线，这样我们可以把两个数组分别分成n个部分，对于两个数组的每个部分，我们选取和较大的并累加至返回结果即可。
比如数组：
[1, 3, 4, 6, 7] [1, 2, 3, 7, 9]
我们将数组中相同的数字连线后，会将其分割成以下形式：
[1], | [3, 4, 6], | [7] [1, 2], | [3], | [7, 9] sum: 1 | 13 | 7 3 | 3 | 16 max: 3 + 13 + 16 = 32
解题时我们使用双指针分别代表两个数组当前的下标。然后再使用两个变量sum1和sum2分别代表当前两个数组的子区间和。循环中，如果当前两个数组指向的数字相同，那么以这两个数字连线为界，可将数组截断。将此时两个区间和sum1和sum2较大一方累加至返回结果。同时两个区间和清零。并且两个数组下标分别加一。如果数组1的数字小于数组2的数字，那么将数组1的数字累加至sum1，同时数组1下标加一。反之，将数组2 的当前数字累加至sum2，同时数组2的下标加一。（解释：由于两个数组都是升序排列，因此移动较小一方的指针，目的是尽快找到数值相同的两个数字）
实现代码：
public int maxSum(int[] nums1, int[] nums2) {
int index1=0,index2=0; // 两个数组当前下标
long sum1=0,sum2=0; // 两个数组的区间和
long sum=0; // 返回结果
while(index1<nums1.length&&index2<nums2.length){
if(nums1[index1]==nums2[index2]){ // 如果两个数字相同
sum1+=nums1[index1]; // 将数组1的当前数字累加至sum1
sum2+=nums2[index2]; // 将数组2的当前数字累加至sum2
sum+=Math.max(sum1,sum2); // 两个区间和的较大值累加至返回结果
sum1=0; // 区间和清零
sum2=0; // 区间和清零
index1++; // 下标加一
index2++; // 下标加一
}else if(nums1[index1]<nums2[index2]){ // 如果数组1当前数字较小
sum1+=nums1[index1]; // 将数组1的当前数字累加至sum1
index1++; // 下标加一
}else{ // 如果数组2当前数字较小
sum2+=nums2[index2]; // 将数组2的当前数字累加至sum1
index2++; // 下标加一
}
}
while(index1<nums1.length){ // 如果数组1还有剩余
sum1+=nums1[index1]; // 将数组1的当前数字累加至sum1
index1++; // 下标加一
}
while(index2<nums2.length){ // 如果数组2还有剩余
sum2+=nums2[index2]; // 将数组2的当前数字累加至sum1
index2++; // 下标加一
}
sum+=Math.max(sum1,sum2); // 两个区间和的较大值累加至返回结果
return (int)(sum%1000000007);
} 本题解法执行时间为3ms。
Runtime: 3 ms, faster than 100.00% of Java online submissions for Get the Maximum Score.
Memory Usage: 49.4 MB, less than 100.00% of Java online submissions for Get the Maximum Score.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1537-get-the-maximum-score-解题思路分析/