---

1594. 矩阵的最大非负积

• 标签：数组、动态规划
• 难度：中等

题目链接

• 1594. 矩阵的最大非负积 - 力扣

题目大意

描述：给定一个 $m \times n$ 的整数矩阵 $grid$。从左上角 $(0,0)$ 出发，每次只能向右或向下移动，到达右下角 $(m-1, n-1)$。路径上所有数字的乘积即为路径的得分。

要求：返回最大非负得分（如果最大得分为负数，返回 $-1$）。结果对 $10^9 + 7$ 取模。

说明：

• $1 \le m, n \le 15$。
• $-4 \le grid[i][j] \le 4$。

示例：

• 示例 1：

输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。

• 示例 2：

输入：grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
输出：8
解释：最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)

解题思路

思路 1：二维 DP（维护最大和最小值）

1. 核心思想

由于有负数存在，最小负数乘以负数可能变成最大正数。因此每个位置需要同时维护最大值和最小值。

定义 $max\_dp[i][j]$ 为从 $(0,0)$ 到 $(i,j)$ 的最大积，$min\_dp[i][j]$ 为最小积。

2. 具体步骤

第 1 步：初始化 $max\_dp[0][0] = min\_dp[0][0] = grid[0][0]$。

第 2 步：初始化第一行和第一列。

第 3 步：遍历 $i = 1 \to m-1$，$j = 1 \to n-1$：

• 从上方 $(i-1,j)$ 和左方 $(i,j-1)$ 转移。
• 当前值 $v = grid[i][j]$。
• 如果 $v > 0$：
  • $max\_dp[i][j] = max(max\_dp[i-1][j], max\_dp[i][j-1]) \times v$
  • $min\_dp[i][j] = min(min\_dp[i-1][j], min\_dp[i][j-1]) \times v$
• 如果 $v < 0$：
  • $max\_dp[i][j] = min(min\_dp[i-1][j], min\_dp[i][j-1]) \times v$
  • $min\_dp[i][j] = max(max\_dp[i-1][j], max\_dp[i][j-1]) \times v$
• 如果 $v == 0$：
  • $max\_dp[i][j] = min\_dp[i][j] = 0$。

第 4 步：返回 $max\_dp[m-1][n-1]$。如果为负数，返回 $-1$。

3. 举例说明

以 $grid = [[1,-2,1],[1,-2,1],[3,-4,1]]$ 为例：

     j=0  j=1  j=2
i=0   1   -2   1
i=1   1   -2   1
i=2   3   -4   1

初始化 $(0,0)$：$max\_dp[0][0] = min\_dp[0][0] = 1$。

第一行 / 第一列（只有单一前驱，按符号规则转移即可）：

位置	前驱	$v$	$max\_dp$	$min\_dp$
$(0,1)$	左 $(0,0)$	$-2$	$1 \times (-2) = -2$	$1 \times (-2) = -2$
$(0,2)$	左 $(0,1)$	$1$	$-2 \times 1 = -2$	$-2 \times 1 = -2$
$(1,0)$	上 $(0,0)$	$1$	$1 \times 1 = 1$	$1 \times 1 = 1$
$(2,0)$	上 $(1,0)$	$3$	$1 \times 3 = 3$	$1 \times 3 = 3$

内部格子（需同时比较上方和左方前驱）：

• $(1,1)$，$v = -2$：上 $(0,1)$ 为 $(-2, -2)$，左 $(1,0)$ 为 $(1, 1)$。
  • $max = \min(-2, 1) \times (-2) = 4$
  • $min = \max(-2, 1) \times (-2) = -2$
• $(1,2)$，$v = 1$：上 $(0,2)$ 为 $(-2, -2)$，左 $(1,1)$ 为 $(4, -2)$。
  • $max = \max(-2, 4) \times 1 = 4$
  • $min = \min(-2, -2) \times 1 = -2$
• $(2,1)$，$v = -4$：上 $(1,1)$ 为 $(4, -2)$，左 $(2,0)$ 为 $(3, 3)$。
  • $max = \min(-2, 3) \times (-4) = 8$（负负得正，取前驱最小值）
  • $min = \max(4, 3) \times (-4) = -16$
• $(2,2)$，$v = 1$：上 $(1,2)$ 为 $(4, -2)$，左 $(2,1)$ 为 $(8, -16)$。
  • $max = \max(4, 8) \times 1 = 8$
  • $min = \min(-2, -16) \times 1 = -16$

最终 $max\_dp$ 与 $min\_dp$ 如下（括号内为 $(max, min)$）：

        j=0      j=1       j=2
i=0   (1, 1)   (-2,-2)   (-2,-2)
i=1   (1, 1)   (4, -2)   (4, -2)
i=2   (3, 3)   (8,-16)   (8,-16)

终点 $max\_dp[2][2] = 8 > 0$，返回 $8$。

对应最优路径：$(0,0) \to (1,0) \to (1,1) \to (2,1) \to (2,2)$，路径积 $1 \times 1 \times (-2) \times (-4) \times 1 = 8$。

思路 1：代码

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        m, n = len(grid), len(grid[0])
        max_dp = [[0] * n for _ in range(m)]
        min_dp = [[0] * n for _ in range(m)]

        max_dp[0][0] = min_dp[0][0] = grid[0][0]

        # 初始化第一行
        for j in range(1, n):
            v = grid[0][j]
            if v >= 0:
                max_dp[0][j] = max_dp[0][j-1] * v
                min_dp[0][j] = min_dp[0][j-1] * v
            else:
                max_dp[0][j] = min_dp[0][j-1] * v
                min_dp[0][j] = max_dp[0][j-1] * v

        # 初始化第一列
        for i in range(1, m):
            v = grid[i][0]
            if v >= 0:
                max_dp[i][0] = max_dp[i-1][0] * v
                min_dp[i][0] = min_dp[i-1][0] * v
            else:
                max_dp[i][0] = min_dp[i-1][0] * v
                min_dp[i][0] = max_dp[i-1][0] * v

        for i in range(1, m):
            for j in range(1, n):
                v = grid[i][j]
                if v >= 0:
                    max_dp[i][j] = max(max_dp[i-1][j], max_dp[i][j-1]) * v
                    min_dp[i][j] = min(min_dp[i-1][j], min_dp[i][j-1]) * v
                else:
                    max_dp[i][j] = min(min_dp[i-1][j], min_dp[i][j-1]) * v
                    min_dp[i][j] = max(max_dp[i-1][j], max_dp[i][j-1]) * v

        ans = max_dp[m-1][n-1]
        return -1 if ans < 0 else ans % MOD

思路 1：复杂度分析

• 时间复杂度：$O(m \times n)$。
• 空间复杂度：$O(m \times n)$，可优化为 $O(n)$。