用 Python 编写程序，从所有可能的有效路径中找出最高分

pythonserver side programmingprogramming更新于 2025/12/1 3:56:17

假设我们有两个数组 nums1 和 nums2。有效路径定义如下 −

选择要遍历的 nums1 或 nums2(从索引 0 开始)。
从左到右遍历数组。

现在，如果我们要遍历 nums1 和 nums2 中存在的任何值，我们可以将路径更改为另一个数组。这里的分数是有效路径中唯一值的总和。我们必须找到所有可能的有效路径中可以获得的最高分数。如果答案太大，则返回模 10^9+7 的结果。

因此，如果输入为 nums1 = [3,5,6,9,11] nums2 = [5,7,9,10]，则输出将为 35，因为 −

从 nums1 开始的有效路径为:[3,5,6,9,11], [3,5,6,9,10], [3,5,7,9,10], [3,5,7,9,11]
从 nums2 开始的有效路径为:[5,7,9,10], [5,6,9,11], [5,6,9,10], [5,7,9,11]

所以最大值是 [3,5,7,9,11]。

为了解决这个问题，我们将遵循以下步骤 −

M := nums1 的大小，N := nums2 的大小
sum1 := 0，sum2 := 0
i := 0，j := 0
res := 0
while i < M and j < N，执行
- 如果 nums1[i] < nums2[j]，则
  - sum1 := sum1 + nums1[i]
  - i := i + 1
- 否则当 nums1[i] > nums2[j]，则
  - sum2 := sum2 + nums2[j]
  - j := j + 1
- 否则，
  - res := res + sum1 的最大值，(sum2 + nums1[i])
  - i := i + 1
  - j := j + 1
  - sum1 := 0
  - sum2 := 0
while i < M ，执行
- sum1 := sum1 + nums1[i]
- i := i + 1
while j < N ，执行
- sum2 := sum2 + nums2[j]
- j := j + 1
return(res + sum1、sum2 的最大值) mod 10^9+7

示例

让我们看看下面的实现以便更好地理解

def solve(nums1, nums2):
   M, N = len(nums1), len(nums2)
   sum1, sum2 = 0, 0
   i, j = 0, 0
   res = 0
   while i < M and j < N:
      if nums1[i] < nums2[j]:
         sum1 += nums1[i]
         i += 1
      elif nums1[i] > nums2[j]:
         sum2 += nums2[j]
         j += 1
      else:
         res += max(sum1, sum2) + nums1[i]
         i += 1
         j += 1
         sum1 = 0
         sum2 = 0

   while i < M:
      sum1 += nums1[i]
      i += 1
   while j < N:
      sum2 += nums2[j]
      j += 1
   return (res + max(sum1, sum2)) % 1000000007

nums1 = [3,5,6,9,11]
nums2 = [5,7,9,10]
print(solve(nums1, nums2))