在 Python 中的矩阵中查找最大非负乘积的程序
假设我们有一个mxn阶矩阵。最初我们在左上角的单元格(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