1537. Get the Maximum Score.md

1537. Get the Maximum Score

https://leetcode.com/problems/get-the-maximum-score/

题目

You are given two sorted arrays of distinct integers nums1 and nums2.

A valid path is defined as follows:

• Choose array nums1 or nums2 to traverse (from index-0).
• Traverse the current array from left to right.
• If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].

Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].

Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

思路

• 用双指针，分别指向两个 Path。

• 分别设置 Path1 和 Path2 的临时变量，a 和 b，表示暂时在 a 中获得的总和、b 中获得的总和。

• 先比较对应位置的值的大小，谁小加谁，再移动。

• 如果对应位置的两个数字相同，我们需要作如下处理：

  • res += max(a, b) + A[i]
  • a = b = 0, i++, j++

  也就是我们要取两条路目前获得的最大值添加到 result 中，并且把当前 A[i] 加到结果中，表示相同的情况默认取 Path1 的值。另外，因为我们已经把 max(a, b) 取过了，所以从此刻开始将 a, b 重置，并且移动两个指针向右。

代码

class Solution:
    def maxSum(self, A: List[int], B: List[int]) -> int:
        i, j = 0, 0
        n, m = len(A), len(B)
        a, b, res, mod = 0, 0, 0, 10**9 + 7
        
        while i < n or j < m:
            if i < n and (j == m or A[i] < B[j]):		# path1 < 2
                a += A[i]
                i += 1
            elif j < m and (i == n or A[i] > B[j]):		# path2 < 1
                b += B[j]
                j += 1
            else:
                res += max(a, b) + A[i]					# path1 == 2
                i += 1
                j += 1
                a, b = 0, 0
                
        return (res + max(a, b)) % mod