↓Skip to main content
  1. Posts/

LeetCode-1594 矩阵的最大非负积

·1 min·
Table of Contents

LeetCode-1594 矩阵的最大非负积 #

Solution 1 #

动态规划, 同时维护非负积和非正积.

代码如下:

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[[-inf, inf] for _ in range(n)] for _ in range(m)]
        if grid[0][0] >= 0:
            dp[0][0][0] = grid[0][0]
        else:
            dp[0][0][1] = grid[0][0]
        for i in range(m):
            for j in range(n):
                if i != 0:
                    if grid[i][j] >= 0: 
                        dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][0] * grid[i][j])
                        dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1] * grid[i][j])
                    if grid[i][j] <= 0:
                        dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][1] * grid[i][j])
                        dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][0] * grid[i][j])
                if j != 0:
                    if grid[i][j] >= 0: 
                        dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][0] * grid[i][j])
                        dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] * grid[i][j])
                    if grid[i][j] <= 0:
                        dp[i][j][0] = max(dp[i][j][0], dp[i][j - 1][1] * grid[i][j])
                        dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][0] * grid[i][j])
        return dp[m - 1][n - 1][0] % 1_000_000_007 if dp[m - 1][n - 1][0] >= 0 else -1