1537. 最大得分

Difficulty
Hard
Tags
前缀树
URL
https://leetcode.cn/problems/get-the-maximum-score/
Star
你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。
一条 合法路径 定义如下：
  • 选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
  • 从左到右遍历当前数组。
  • 如果你遇到了 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。
得分定义为合法路径中不同数字的和。
请你返回所有可能合法路径中的最大得分。
由于答案可能很大，请你将它对 10^9 + 7 取余后返回。
示例 1：
notion imagenotion image
输入：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：
输出：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 都是严格递增的数组。
通过次数5,411提交次数14,176

法 1 前缀和

思路
分段求和。
因为值相同的点肯定是要加上的。那么两个相同值中间的段到底是选择 nums1呢还是nums2，当然是取和较大的那段了。
所以整体思路就是，先将值相同的点 存下来，然后遍历每一段，取每一段中较大的段和。
题解
class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        prefix_1 = [0] * (len(nums1) + 1)
        prefix_2 = [0] * (len(nums2) + 1)

        for i in range(1, len(prefix_1)):
            prefix_1[i] = prefix_1[i-1] + nums1[i-1]

        for j in range(1, len(prefix_2)):
            prefix_2[j] = prefix_2[j-1] + nums2[j-1]

        i, j = 0, 0
        same_val = [[-1, -1]]
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                same_val.append([i, j])
                i += 1
                j += 1
            elif nums2[j] > nums1[i]:
                i += 1
            elif nums2[j] < nums1[i]:
                j += 1
        
        same_val.append([len(nums1), len(nums2)])

        # 遍历每一段，取较大的段和,别忘了还有节点值也要加上
        res = 0
        for i in range(1, len(same_val)):
            n_1 = prefix_1[same_val[i][0]-1+1] - prefix_1[same_val[i-1][0]+1]
            n_2 = prefix_2[same_val[i][1]-1+1] - prefix_2[same_val[i-1][1]+1]
            res += max(n_1, n_2)
            if same_val[i][0] < len(nums1):
                res += nums1[same_val[i][0]]

            

        return res % (10**9 + 7)