Leetcode 1716 Solution

This article provides solution to leetcode question 1716 (maximum-non-negative-product-in-a-matrix)
Categories:
Tags:
Access this page by simply typing in "lcs 1716" in your browser address bar if you have bunnylol configured.

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