Leetcode 1716 Solution

This article provides solution to leetcode question 1716 (maximum-non-negative-product-in-a-matrix)

https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix

Solution

import numpy as np
class Solution: def maxProductPath(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0])
dp1 = np.ndarray((m, n)).tolist() dp2 = np.ndarray((m, n)).tolist()
dp1[0][0] = dp2[0][0] = grid[0][0]
for i in range(1, m): dp1[i][0] = dp2[i][0] = grid[i][0] * dp1[i - 1][0] for j in range(1, n): dp1[0][j] = dp2[0][j] = grid[0][j] * dp1[0][j - 1]
for i in range(1, m): for j in range(1, n): options = [ dp1[i][j - 1] * grid[i][j], dp1[i - 1][j] * grid[i][j], dp2[i][j - 1] * grid[i][j], dp2[i - 1][j] * grid[i][j], ]
dp1[i][j] = max(options) dp2[i][j] = min(options)
if dp1[-1][-1] >= 0: return dp1[-1][-1] % (10**9 + 7) else: return -1