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

2つの配列 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](合計 35)です。

解き方のアプローチ

この問題は、両方の配列が昇順にソートされていることを前提に、マージ処理のような「二ポインタ」テクニックを使うことで効率的に解けます。共通の値が出現する地点が分岐点となり、そこまでの各区間の合計のうち大きい方を採用していくイメージです。具体的な手順は以下の通りです。

• M := nums1 のサイズ、N := nums2 のサイズとする。

• sum1 := 0、sum2 := 0 と初期化する。

• i := 0、j := 0 と初期化する。

• res := 0 と初期化する。

• i < M かつ 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 + max(sum1, sum2) + nums1[i]、i := i + 1、j := j + 1、sum1 := 0、sum2 := 0。

• i < M の間、sum1 := sum1 + nums1[i]、i := i + 1 を繰り返す。

• j < N の間、sum2 := sum2 + nums2[j]、j := j + 1 を繰り返す。

• (res + max(sum1, sum2)) mod 10^9+7 を返す。

実装例(Python)

理解を深めるために、以下の実装を見てみましょう。

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

計算量

このアルゴリズムの時間計算量は O(M+N)、空間計算量は O(1) であり、大きな入力に対しても高速に動作します。