用 Python 编写程序，在矩阵中查找最大非负积

pythonserver side programmingprogramming更新于 2025/11/30 0:12:17

假设我们有一个 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 填充
对于范围在 0 到 m - 1 内的 i，执行
- 对于范围在 0 到 n - 1 内的 j，执行
  - 如果 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]
    - maximum := ans1、ans2、ans3 和 ans4 中的最大值
    - minimum := ans1、ans2、ans3 和 ans4 中的最小值
    - 如果最大值 < 0，则
      - dp[i, j] := 组成一对 (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

示例

让我们看看下面的实现以便更好地理解 −

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