Pythonで可能なすべての有効なパスから最大スコアを見つけるプログラム

2つの配列nums1とnums2があるとします。有効なパスは次のように定義されます-

• トラバースするnums1またはnums2を選択します（インデックス0から）。

• 配列を左から右にトラバースします。

ここで、nums1とnums2に存在する値を移動している場合は、他の配列へのパスを変更できます。ここで、スコアは有効なパスの一意の値の合計です。考えられるすべての有効なパスから取得できる最大スコアを見つける必要があります。答えが大きすぎる場合は、10 ^ 9+7を法とする結果を返します。

したがって、入力がnums1 =[3,5,6,9,11] nums2 =[5,7,9,10]の場合、-

• 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

• i

  • nums1 [i]

    • 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

• 私が

  • sum1：=sum1 + nums1 [i]

  • i：=i + 1

• j

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

入力

[3,5,6,9,11], [5,7,9,10]

出力

35