在Python中找到矩阵中最大非负乘积的程序

假设我们有一个m x n的矩阵。最开始我们在左上角的单元格(0,0)，每一步中，我们只能向右或向下移动矩阵。我们要在所有可能的路径中从左上角单元格(0,0)到右下角单元格(m-1,n-1)中找到最大的非负乘积路径。如果答案太大，则返回最大非负乘积模10^9+7。

因此，如果输入为

2	-4	2
2	-4	2
4	-8	2

那么输出将是256，因为路径如图所示,

2	-4	2
2	-4	2
4	-8	2

因此，乘积为[2 * 2 * (-4) * (-8) * 2] = 256。

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

p := 10^9+7
m := 矩阵的行数
n := 矩阵的列数
dp := 给定矩阵的二维矩阵，并填充为0
for i in range 0 to m – 1, do
- for j in range 0 to n – 1, do
  - 如果i和j都等于0，那么
  - dp[i, j] := make a pair (matrix[i, j], matrix[i, j])
  - 否则当i等于0时，那么
  - ans1 := dp[i, j-1, 0] * matrix[i, j]
  - dp[i, j] := make a pair (ans1, ans1)
  - 否则当j等于0时，那么
  - ans1 := dp[i-1, j, 0] * matrix[i, j]
  - dp[i, j] := make a pair (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、ans2、ans3和ans4中的最大值
  - minimum := ans1、ans2、ans3和ans4中的最小值
  - 如果maximum <0，则
    - dp[i, j] := make a pair (minimum, minimum)
  - 否则当minimum > 0时，那么
    - dp[i, j] := make a pair (maximum, maximum)
  - 否则，
    - dp[i, j] := make a pair (maximum, minimum)
如果dp[m-1, n-1, 0] < 0，则
- 返回-1
否则，
- 返回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))