在 Python 中的矩阵中查找最大非负乘积的程序
假设我们有一个 mx 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。
示例
让我们看看以下实现以获得更好的理解 -
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
以上是 在 Python 中的矩阵中查找最大非负乘积的程序 的全部内容， 来源链接： utcz.com/z/357432.html
