Pythonの行列で最大の非負の積を見つけるプログラム

次数mxnの行列があるとします。最初は左上隅のセル（0、0）にあり、各ステップで、マトリックス内で右または下にのみ移動できます。ここで、左上隅のセル（0、0）から右下隅のセル（m-1、n-1）までのすべての可能なパスの中から、負でない積が最大になるパスを見つける必要があります。答えが大きすぎる場合は、10 ^ 9+7を法とする最大の非負の積を返します。

したがって、入力が次のような場合

パスが色付きであるため、出力は256になります。

したがって、積は[2 * 2 *（-4）*（-8）* 2]=256です。

これを解決するには、次の手順に従います-

• p：=10 ^ 9 + 7
• m：=行列の行数
• n：=行列の列数
• dp：=2次元行列は、指定された行列と次数であり、0で埋められます
• 0からm-1の範囲のiの場合、do
  • 0からn-1の範囲のjの場合、do
    • iが0と同じで、jが0と同じ場合、
      • dp [i、j]：=ペアを作成します（matrix [i、j]、matrix [i、j]）
    • それ以外の場合、iが0と同じ場合、
      • ans1：=dp [i、j-1、0] * matrix [i、j]
      • dp [i、j]：=ペアを作成する（ans1、ans1）
    • それ以外の場合、jが0と同じ場合、
      • 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]
      • 最大：=ans1、ans2、ans3、ans4の最大値
      • 最小：=ans1、ans2、ans3、ans4の最小値
      • 最大値が0未満の場合、
        • dp [i、j]：=ペアを作成します（最小、最小）
      • それ以外の場合、最小値> 0の場合、
        • dp [i、j]：=ペアを作成します（最大、最大）
      • それ以外の場合、
        • dp [i、j]：=ペアを作成します（最大、最小）
• dp [m-1、n-1、0] <0の場合、
  • 戻り値-1
• それ以外の場合、
  • return dp [m-1、n-1、0]％p

例

理解を深めるために、次の実装を見てみましょう-

def solve(matrix):
   p = 1e9+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))

入力

"pqpqrrr"

出力

256