“This is the 30th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

describe

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).

The 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: ,4,5,8,9,4,5,8,10 [2], [2], [2,4,6,8,9], [2,4,6,8,10], (starting from nums1),6,8,9 [4], [4,5,8,10], [4,5,8,9]. [4,6,8,10] The maximum is obtained with The path in green.Copy the code

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].
Copy the code

Example 3:

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

Example 4:

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

Note:

1 <= nums1.length, nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.
Copy the code

parsing

Given a sorted array of two different integers nums1 and nums2. Valid paths are defined as follows:

  • Select the array nums1 or nums2 to traverse (starting at index 0).
  • Traverses the current array from left to right.
  • If you are reading a value that exists in both nums1 and nums2, you can change the path to another array. (Only one duplicate value is considered in the valid path).

A score is defined as the sum of different values in a valid path, and returns the maximum score you can get for all possible valid paths. Since the answer may be too large, modulo it 10^9 + 7 and return.

The conversion position of the two arrays is exactly the same as that of the two arrays. This ensures that the valid paths are always in ascending order. The roughest way to do this is to find all the possible paths and then find the array that has the largest sum. But as long as there are two arrays with the same number, two paths diverge, which is O(2 to the n), which is definitely a timeout.

Each time we find A number shared by two arrays, we calculate the sum of the digits before that number, and compare them to get A larger sum. Repeat the process, as shown in the following two strings A and B, where the O represents the same character:

  • A: XXXXOZZZZOXXX
  • B: TTTOSSSSOPPP

Now compare the sum of XXXXO and TTTO respectively, take the maximum value as the maximum sum a when finding the first O, then compare the sum of ZZZZO and SSSSO respectively, take the maximum value and add a as the maximum sum B when finding the second O. Then add the remaining numbers XXX and PPP to get S1 and S2, and the larger value is the result.

answer

class Solution(object):
    def maxSum(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        i = j = s1 = s2 = 0
        m = len(nums1)
        n = len(nums2)
        while i<m or j<n:
            if i==m:
                s2 += nums2[j]
                j += 1
            elif j==n:
                s1 += nums1[i]
                i += 1
            elif nums1[i] < nums2[j]:
                s1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                s2 += nums2[j]
                j += 1
            elif nums1[i] == nums2[j]:
                s1 = max(s1+nums1[i], s2+nums2[j])
                s2 = s1
                i += 1
                j += 1
        return max(s1, s2)%(10**9+7)
        
        	      
		
Copy the code

The results

Given the submission in the Python online submissions in the linked list. Given in the Python online submissions for Get the Maximum Score.Copy the code

Original link: leetcode.com/problems/ge…

Your support is my biggest motivation