矩阵的最大非负积1

题目描述

题目讲解

矩阵中有正数、负数、0。

乘积遇到负数会翻转符号，因此：

1. 当前格子的 最大乘积 可能来自上方或左方的 最小乘积 × 当前负数。
2. 当前格子的 最小乘积 可能来自上方或左方的 最大乘积 × 当前负数。

故需要维护两个 DP 数组：

1. dpMax[i][j] ---> 到达 (i,j) 的最大乘积.
2. dpMin[i][j] ---> 到达 (i,j) 的最小乘积.

只能从第一行向左走，从第一列向下走.

设当前值为 v = grid[i][j]

从上方来:

candidates from top = {dpMax[i-1][j] * v, dpMin[i-1][j] * v}

从左边来:

candidates from left = {dpMax[i][j-1] * v, dpMin[i][j-1] * v}

具体流程

代码

c++
python
java
class Solution:
    def maxProductPath(self, grid):
        MOD = 10**9 + 7
        m, n = len(grid), len(grid[0])

        dpMax = [[0] * n for _ in range(m)]
        dpMin = [[0] * n for _ in range(m)]

        dpMax[0][0] = dpMin[0][0] = grid[0][0]

        # 第一行
        for j in range(1, n):
            dpMax[0][j] = dpMin[0][j] = dpMax[0][j-1] * grid[0][j]

        # 第一列
        for i in range(1, m):
            dpMax[i][0] = dpMin[i][0] = dpMax[i-1][0] * grid[i][0]

        # 其他格子
        for i in range(1, m):
            for j in range(1, n):
                v = grid[i][j]
                candidates = [
                    dpMax[i-1][j] * v,
                    dpMin[i-1][j] * v,
                    dpMax[i][j-1] * v,
                    dpMin[i][j-1] * v
                ]
                dpMax[i][j] = max(candidates)
                dpMin[i][j] = min(candidates)
        # 取出 dpMax 最后一行, 最后一列 的值，即 到达终点(m-1, n-1)的最大乘积.
        result = dpMax[m-1][n-1]
        return result % MOD if result >= 0 else -1

链接

  1. 矩阵的最大非负积https://leetcode.cn/problems/maximum-non-negative-product-in-a-matrix/description/ ↩︎