Python 矩阵中最大非负积的程序

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

因此，如果输入如下所示：

2-42
2-42
4-82

那么输出将是256，因为路径是彩色的那条，

2-42
2-42
4-82

所以乘积是 [2 * 2 * (-4) * (-8) * 2] = 256。

为了解决这个问题，我们将遵循以下步骤：

  • p := 10^9+7
  • m := 矩阵的行数
  • n := 矩阵的列数
  • dp := 一个与给定矩阵同阶的二维矩阵，并填充0
  • 对于 i 从 0 到 m - 1：
    • 对于 j 从 0 到 n - 1：
      • 如果 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 的最小值
        • 如果 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

示例

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

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

更新于：2021年10月4日

浏览量：133

开启你的职业生涯

完成课程获得认证

开始学习
广告