最大得分

难度: Hard

你有两个有序且数组内元素互不相同的数组 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]得到。

提示：

1 <= nums1.length, nums2.length <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁷
nums1 和 nums2 都是严格递增的数组。

Submission

运行时间: 65 ms

内存: 25.1 MB

class Solution:
    def maxSum(self, nums1, nums2):
        best1, best2=0,0
        m,n=len(nums1), len(nums2)
        i, j=0,0
        big=10**9 + 7
        while i<m and j<n:
            if i<m and j<n:
                if nums1[i]<nums2[j]:
                    best1+=nums1[i]
                    i+=1
                elif nums1[i]>nums2[j]:
                    best2+=nums2[j]
                    j+=1
                else:
                    best=max(best1, best2)+nums1[i]
                    best1, best2= best, best
                    i, j = i+1, j+1
        while i<m:
            best1+=nums1[i]
            i+=1
        while j<n:
            best2+=nums2[j]
            j+=1
        return max(best1, best2)%big

Explain

此题解使用双指针技术遍历两个有序数组nums1和nums2，同时维护两个累加器best1和best2来记录从每个数组开始的可能的最大分数。遍历过程中，根据当前指针指向的元素大小，增加较小值到对应的累加器。当两数组在某位置的元素相等时，可以从一个数组切换到另一个，因此更新best1和best2为这两者的最大值加当前共同元素。这样保证了在遇到共同元素时，选择到目前为止可能得到的最大分数继续累积。遍历完两数组后，比较两个累加器的值，取最大值作为结果。由于结果可能很大，最终对10^9 + 7取模。

时间复杂度: O(m + n)

空间复杂度: O(1)

class Solution:
    def maxSum(self, nums1, nums2):
        best1, best2 = 0, 0  # 初始化两个路径的最大得分
        m, n = len(nums1), len(nums2)  # 获取两个数组的长度
        i, j = 0, 0  # 初始化两个数组的指针
        big = 10**9 + 7  # 定义取余的数
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                best1 += nums1[i]  # 累加nums1的当前元素到best1
                i += 1
            elif nums1[i] > nums2[j]:
                best2 += nums2[j]  # 累加nums2的当前元素到best2
                j += 1
            else:
                best = max(best1, best2) + nums1[i]  # 遇到相同元素时，选择最大的累计得分继续
                best1, best2 = best, best  # 更新两个路径的得分
                i += 1
                j += 1
        while i < m:
            best1 += nums1[i]  # 处理nums1剩余的元素
            i += 1
        while j < n:
            best2 += nums2[j]  # 处理nums2剩余的元素
            j += 1
        return max(best1, best2) % big  # 返回两个路径中的最大值，并取模

Explore

双指针技术在这题中的使用是为了同时遍历两个有序数组，并通过比较当前指针所指向的元素来决定分数的累加。当一个数组的元素小于另一个数组的元素时，较小元素被加入其对应的累加器，这样确保了在每一步都在尽可能地增加总分。当两数组元素相等时，选择到目前为止两个累加器中的最大值继续累积，因为这表示两个路径均可选择，而选择最大的累计得分可以确保不遗漏可能的最大分数路径。此外，算法最后还会处理任一数组中剩余的元素，保证所有可能的分数都被计算。

当两数组元素相等时，这表示存在一个交叉点，即可以从一个数组切换到另一个数组而不损失任何分数。在这种情况下，更新best1和best2为两者的最大值加当前共同元素，是为了确保无论之后选择哪条路径，都是从最高可能分数开始。如果简单地累加当前元素到各自的累加器，会导致一个问题：可能会错过从一个数组到另一个数组的最优切换时机，因此使用最大值确保在任一切换点，所取的路径始终是分数最高的路径。

当其中一个数组的元素已经完全遍历时，另一个数组中剩余的元素不再有可能与已遍历完的数组的任何元素相遇或形成交叉点。因此，剩余元素可以直接累加到对应的累加器中，因为它们不会影响到另一个已经没有元素可遍历的数组的分数。这意味着，一旦一个数组遍历完毕，剩下的数组只需要简单地加总其剩余元素即可。

题解中通过在两个while循环外额外添加了两个独立的循环来处理这种情况。如果一个数组的指针已经到达末尾而另一个数组还有元素未遍历，算法将继续单独遍历剩下的数组，并将所有剩余的元素值累加到对应的累加器中。这种处理方式确保了即使两个数组长度不等，也能够正确计算出所有可能的分数，并最终比较两个累加器得到最大值。