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

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

所以，如果输入是这样的

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

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

示例

让我们看看以下实现以获得更好的理解 -

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