Pythonで行列の経路における最大の非負の積を求めるプログラム

問題概要

m × n の行列が与えられます。スタート地点は左上のセル (0, 0) で、各ステップでは右または下にのみ移動できます。左上のセル (0, 0) から右下のセル (m-1, n-1) に至るすべての経路の中から、通過するセルの値の積が最大となる「非負の積」を持つ経路を見つけます。答えが非常に大きくなる場合は、最大の非負の積を 10^9+7 で割った余りを返します。

例

たとえば、入力が次の行列だったとします。

このとき出力は 256 になります。下の表で色を付けた経路を選んだ場合、積は次のように計算されます。

積は [2 × 2 × (-4) × (-8) × 2] = 256 となります。

解き方（アルゴリズム）

この問題は動的計画法（DP）で解きます。ポイントは、各セルについて「そのセルに到達できる積の最大値」と「最小値」の両方を記録することです。負の数同士を掛けると正になるため、現時点での最小値（絶対値が大きい負の数）が、後の負の数との掛け合わせによって最大値に変わる可能性があるからです。

具体的な手順は以下の通りです。

• p := 10^9+7（剰余計算用の定数）
• m := 行列の行数、n := 行列の列数
• dp := 元の行列と同じサイズの2次元配列を用意して 0 で初期化する。各要素は (最大値, 最小値) のペアを保持する
• i を 0 から m-1 まで、j を 0 から n-1 まで順に処理します。
  • i == 0 かつ j == 0 の場合：dp[i][j] := (matrix[i][j], matrix[i][j])
  • i == 0 の場合（1行目）：ans1 := dp[i][j-1][0] × matrix[i][j] とし、dp[i][j] := (ans1, ans1)
  • j == 0 の場合（1列目）：ans1 := dp[i-1][j][0] × matrix[i][j] とし、dp[i][j] := (ans1, ans1)
  • それ以外の場合：
    • 上から来るケース：ans1 := dp[i-1][j][0] × matrix[i][j]、ans2 := dp[i-1][j][1] × matrix[i][j]
    • 左から来るケース：ans3 := dp[i][j-1][0] × matrix[i][j]、ans4 := dp[i][j-1][1] × matrix[i][j]
    • maximum := ans1〜ans4 の最大値、minimum := ans1〜ans4 の最小値
    • maximum < 0 の場合（候補がすべて負）：dp[i][j] := (minimum, minimum)。最も絶対値が大きい負の値を残すことで、将来の負の数との掛け合わせで大きな正の値を狙えます
    • minimum > 0 の場合（候補がすべて正）：dp[i][j] := (maximum, maximum)
    • それ以外の場合（正負が混在）：dp[i][j] := (maximum, minimum)
• 最後に、dp[m-1][n-1][0] < 0 なら -1 を返し、そうでなければ dp[m-1][n-1][0] % p を返します。

実装例（Python）

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

def solve(matrix):
    p = 10**9 + 7
    m = len(matrix)
    n = len(matrix[0])

    dp = [[0 for _ in range(n)] for _ in range(m)]

    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[i][j] = [matrix[i][j], matrix[i][j]]

            elif i == 0:
                ans1 = dp[i][j-1][0] * matrix[i][j]
                dp[i][j] = [ans1, ans1]

            elif j == 0:
                ans1 = dp[i-1][j][0] * matrix[i][j]
                dp[i][j] = [ans1, ans1]

            else:
                ans1 = dp[i-1][j][0] * matrix[i][j]
                ans2 = dp[i-1][j][1] * matrix[i][j]
                ans3 = dp[i][j-1][0] * matrix[i][j]
                ans4 = dp[i][j-1][1] * matrix[i][j]
                maximum = max(ans1, ans2, ans3, ans4)
                minimum = min(ans1, ans2, ans3, ans4)
                if maximum < 0:
                    dp[i][j] = [minimum, minimum]
                elif minimum > 0:
                    dp[i][j] = [maximum, maximum]
                else:
                    dp[i][j] = [maximum, minimum]

    if dp[m-1][n-1][0] < 0:
        return -1
    else:
        return int(dp[m-1][n-1][0] % p)

matrix = [[2,-4,2],[2,-4,2],[4,-8,2]]
print(solve(matrix))

入力と出力

入力：

matrix = [[2,-4,2],[2,-4,2],[4,-8,2]]

出力：

256

まとめ

本アルゴリズムの時間計算量は O(m×n)、空間計算量も O(m×n) です。各セルで最大値と最小値のペアを管理することで、負の数が絡む積の問題にも柔軟に対応できます。非負の積が存在しない場合は -1 を返す仕様になっており、実務でも応用しやすいパターンです。