LeetCode 1594. 矩阵的最大非负积

2026-01-12 HGNULB 约 10 分钟

文章信息 8 个分类 3 个标签

分类

题目描述

✅ 1594. 矩阵的最大非负积

题意分析

从矩阵左上角走到右下角，每步只能向右或向下，把沿途所有格子的值连乘起来，问能拿到的最大乘积是多少。如果所有路径的乘积都是负数，返回 -1。

和常见的路径求和题相比，这里的合成方式是乘法，而格子里可能出现负数和 0。负负得正意味着「当前更小」未必是坏事，一个很负的中间结果碰上后面一个负数就会翻身成很大的正数，这是本题全部的难点来源。

返回值的口径要额外小心：只有最终结果为负才返回 -1，中途出现负数完全正常；非负的结果需要对 $10^9+7$ 取模再返回，而取模只能发生在最后一步，绝不能在中间过程做，否则大小关系被打乱，比较就失去意义。

规模上行列都不超过 15，路径长度最多 29 个格子，每个格子的绝对值不超过 4，所以乘积的绝对值上界是 $4^{29} \approx 2.9 \times 10^{17}$，超出 32 位但仍在 64 位范围内，中间量必须用 64 位整型存。

解法：最大最小乘积动态规划

核心思路

暴力做法是把所有路径枚举出来逐条求积。路径条数是 $\binom{m+n-2}{m-1}$，$15 \times 15$ 的矩阵大约有 4000 万条，写出来能过但完全没有必要，而且思路上没体现出这题真正的考点。

自然的改进是设 $f[i][j]$ 表示走到 $(i,j)$ 的最大乘积，转移取 $\max(f[i-1][j], f[i][j-1]) \times grid[i][j]$。这个式子是错的：当 $grid[i][j] < 0$ 时，乘一个负数会把大小关系整个翻转过来，此刻真正应该被选中的是前驱里最小的那个乘积，而它并没有被记下来。

观察到这一点，状态就该扩成一对。定义 $maxDp[i][j]$ 为从起点走到 $(i,j)$ 的所有路径乘积中的最大值，$minDp[i][j]$ 为其中的最小值。之所以最小值也要记，是因为它是「未来遇到负数时的最优候选」，两者共同构成一个完整的、可继续推进的状态。

转移时把两个前驱的两个极值分别乘上当前格子，得到四个候选：$maxDp[i-1][j] \cdot v$、$minDp[i-1][j] \cdot v$、$maxDp[i][j-1] \cdot v$、$minDp[i][j-1] \cdot v$。取四者最大写进 $maxDp[i][j]$，取四者最小写进 $minDp[i][j]$。之所以直接取四选一而不去讨论 $v$ 的正负，是因为无论 $v$ 是正是负是零，最优值一定落在这四个候选之中，省掉分类讨论反而更不容易写错。

最后一个细节是第一行和第一列。它们只有一条路径可达，$maxDp$ 和 $minDp$ 必然相等，而且没有两个前驱可供比较，必须单独初始化；如果让它们走通用的四值转移，会读到还没填过的越界位置。

解题步骤

开两张 $m \times n$ 的 64 位表 maxDp 和 minDp，语义分别是到该格为止路径乘积的最大值与最小值。用 64 位是因为乘积可达 $4^{29}$ 量级，32 位会静默溢出。

把 maxDp[0][0] 和 minDp[0][0] 都设成 grid[0][0]。起点只有一条「空路径 + 自身」的走法，最大最小自然相同。

沿第一列自上而下递推 maxDp[i][0] = maxDp[i-1][0] * grid[i][0]，并让 minDp[i][0] 取同一个值。第一列每格只能从正上方来，路径唯一，极大极小必然重合。

第一行同理自左向右递推。单独处理这两条边，是为了让后面的双层循环从 $(1,1)$ 起步时，上方和左方两个前驱都保证已经填好。

双层循环遍历 $i$ 从 1 到 $m-1$、$j$ 从 1 到 $n-1$，每格算出四个候选乘积。同时用两个前驱的极大和极小，正是为了兜住负数翻转的情形。

四个候选取最大填 maxDp[i][j]，取最小填 minDp[i][j]。两张表必须在同一轮里一起更新，少更新哪一张，后续的翻转候选就丢了。

读 maxDp[m-1][n-1]：小于 0 直接返回 -1，否则返回它对 $10^9+7$ 取模的结果。取模放在最后一步，是因为模运算不保序，中途取模会让 max 和 min 选错分支。

以 grid = [[1,-2,1],[1,-2,1],[3,-4,1]] 走一遍：起点 maxDp[0][0] = minDp[0][0] = 1。第一列：$maxDp[1][0] = 1 \times 1 = 1$，$maxDp[2][0] = 1 \times 3 = 3$，minDp 同值。第一行：$maxDp[0][1] = 1 \times (-2) = -2$，$maxDp[0][2] = -2 \times 1 = -2$，minDp 同值。进入 $(1,1)$，$v = -2$：上方给出 $(-2) \times (-2) = 4$ 和 $4$，左方给出 $1 \times (-2) = -2$ 和 $-2$，于是 maxDp[1][1] = 4、minDp[1][1] = -2。$(1,2)$，$v = 1$：上方给出 $-2, -2$，左方给出 $4, -2$，得 maxDp[1][2] = 4、minDp[1][2] = -2。$(2,1)$，$v = -4$：上方拿 $(1,1)$ 的 $4$ 和 $-2$，分别得 $-16$ 和 $8$——注意正是那个不起眼的 $-2$ 乘上 $-4$ 翻成了 8；左方拿 $(2,0)$ 的 $3, 3$，得 $-12, -12$。四者取极值得 maxDp[2][1] = 8、minDp[2][1] = -16。$(2,2)$，$v = 1$：上方给出 $4, -2$，左方给出 $8, -16$，得 maxDp[2][2] = 8、minDp[2][2] = -16。终点最大值 8 非负，返回 $8 \bmod (10^9+7) = 8$。若当初只维护 maxDp，$(2,1)$ 处只会拿到 $\max(4, 3) \times (-4) = -16$，最终会误判成没有非负路径。

代码实现

class Solution {
    // 乘到负数时，之前的最小乘积可能变成最大乘积。
    public int maxProductPath(int[][] grid) {
        int mod = 1_000_000_007;
        int m = grid.length;
        int n = grid[0].length;

        long[][] maxDp = new long[m][n];
        long[][] minDp = new long[m][n];
        maxDp[0][0] = grid[0][0];
        minDp[0][0] = grid[0][0];

        for (int i = 1; i < m; i++) {
            maxDp[i][0] = maxDp[i - 1][0] * grid[i][0];
            minDp[i][0] = maxDp[i][0];
        }
        for (int j = 1; j < n; j++) {
            maxDp[0][j] = maxDp[0][j - 1] * grid[0][j];
            minDp[0][j] = maxDp[0][j];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                long val = grid[i][j];
                long fromUpMax = maxDp[i - 1][j] * val;
                long fromUpMin = minDp[i - 1][j] * val;
                long fromLeftMax = maxDp[i][j - 1] * val;
                long fromLeftMin = minDp[i][j - 1] * val;

                maxDp[i][j] = Math.max(Math.max(fromUpMax, fromUpMin), Math.max(fromLeftMax, fromLeftMin));
                minDp[i][j] = Math.min(Math.min(fromUpMax, fromUpMin), Math.min(fromLeftMax, fromLeftMin));
            }
        }

        long answer = maxDp[m - 1][n - 1];
        if (answer < 0) {
            return -1;
        }
        return (int) (answer % mod);
    }
}

func maxProductPath(grid [][]int) int {
    // 乘到负数时，之前的最小乘积可能变成最大乘积。
    const mod = 1000000007
    m, n := len(grid), len(grid[0])

    maxDp := make([][]int64, m)
    minDp := make([][]int64, m)
    for i := 0; i < m; i++ {
        maxDp[i] = make([]int64, n)
        minDp[i] = make([]int64, n)
    }
    maxDp[0][0] = int64(grid[0][0])
    minDp[0][0] = int64(grid[0][0])

    for i := 1; i < m; i++ {
        maxDp[i][0] = maxDp[i-1][0] * int64(grid[i][0])
        minDp[i][0] = maxDp[i][0]
    }
    for j := 1; j < n; j++ {
        maxDp[0][j] = maxDp[0][j-1] * int64(grid[0][j])
        minDp[0][j] = maxDp[0][j]
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            val := int64(grid[i][j])
            fromUpMax := maxDp[i-1][j] * val
            fromUpMin := minDp[i-1][j] * val
            fromLeftMax := maxDp[i][j-1] * val
            fromLeftMin := minDp[i][j-1] * val

            maxDp[i][j] = max64(max64(fromUpMax, fromUpMin), max64(fromLeftMax, fromLeftMin))
            minDp[i][j] = min64(min64(fromUpMax, fromUpMin), min64(fromLeftMax, fromLeftMin))
        }
    }

    answer := maxDp[m-1][n-1]
    if answer < 0 {
        return -1
    }
    return int(answer % mod)
}

func max64(a int64, b int64) int64 {
    if a > b {
        return a
    }
    return b
}

func min64(a int64, b int64) int64 {
    if a < b {
        return a
    }
    return b
}

复杂度分析

时间复杂度：$O(mn)$，每个格子只被访问一次，格内做 4 次乘法和常数次比较，边界初始化再花 $O(m + n)$。

空间复杂度：$O(mn)$，两张同尺寸的 64 位表。由于转移只依赖上一行和当前行左侧，可以滚动成 $O(n)$，但表小到 $15 \times 15$，滚动带来的收益远不如可读性重要。

关键点总结

乘法型 DP 的通用模板是「同时维护最大和最小」。只要转移里出现可能为负的乘数，单一极值状态就不闭合，必须成对推进。

判断状态是否完备的标准是：已记录的量能不能唯一决定下一步的最优值。这题最大值单独一个不够，补上最小值之后才闭合，这个思路和最大子数组乘积、含负权的区间 DP 完全一致。

四个候选直接取极值，比按 $grid[i][j]$ 的正负分类讨论更短也更稳，尤其是 0 这个既非正也非负的取值最容易在分类里写漏。

取模必须放在最后一步。模运算破坏序关系，中途取模会让 max/min 比较的是残值而不是真实大小。

边界行列没有可比较的前驱，必须单独初始化；这是网格 DP 里最高频的越界与错值来源。

面试视角：面试官往往先让你写出单表 DP，再给一个含负数的反例逼你修。能主动说出「乘法要维护极小值」并给出翻转的具体例子，是这题的核心得分点；紧接着的追问通常是溢出范围和取模时机。

易错点总结

错误写法：只维护一张 maxDp，转移写成 max(上, 左) * v：grid = [[1,-2,1],[1,-2,1],[3,-4,1]] → $(2,1)$ 处会拿 $\max(4,3) \times (-4) = -16$，最终终点得到负值，返回 -1，而正确答案是 8。

错误写法：中间过程就对 $10^9+7$ 取模：一旦某个乘积超过模数被折回小值，max 会在残值之间比较 → 选出的路径不再是真正乘积最大的那条，返回值随机偏离，而且负数取模在 Java 里还会保留负号。

错误写法：用 int 存中间乘积 → 路径长 29、每格取 4 时乘积达 $4^{29}$，32 位静默溢出成看似合法的正负数，答案完全不可控。

错误写法：第一行第一列也走通用四值转移 → 读 maxDp[-1][0] 或 maxDp[0][-1]，Java 抛数组越界，Go 直接 panic。

错误写法：第一列初始化时把 minDp[i][0] 写成 0 或极大值而不是与 maxDp[i][0] 同值 → 沿第一列下来再右拐的那些路径，其最小乘积被伪造，后续负数翻转会算出根本不存在的路径。

错误写法：把「中途出现负数」当成失败并提前返回 -1 → grid = [[1,-2,1],[1,-2,1],[3,-4,1]] 的最优解正是靠两次负数抵消得来的，提前退出会直接丢掉答案。

错误写法：终点判负写成 maxDp[m-1][n-1] <= 0 → grid = [[0]] 这类乘积为 0 的情形被误判成 -1，而 0 是非负的，应当返回 0。

错误写法：return (int) answer % mod，把强制类型转换写在取模之前 → 先截断成 32 位再取模，大乘积被截断后结果错误；正确写法是先 answer % mod 再转换。

错误写法：更新时先写 maxDp[i][j]，再用刚被覆盖的 maxDp[i][j] 参与计算 minDp[i][j] → 四个候选必须在两次写入之前全部算好并缓存，否则 minDp 读到的是本轮新值而非前驱值。

相似题目

题目	难度	考察点
62. 不同路径	中等	转移是计数求和，也可以直接用组合数一步算出
63. 不同路径 II	中等	障碍格状态置零，且第一行第一列要提前截断
64. 最小路径和	中等	加法且全为正数，单一极值状态就足够闭合
120. 三角形最小路径和	中等	非矩形网格，自底向上递推可省掉边界判断
174. 地下城游戏	困难	正着推不闭合，必须倒着定义「所需最低初始值」
688. 骑士在棋盘上的概率	中等	状态多一维步数，转移是八方向概率均摊
931. 下降路径最小和	中等	前驱是上一行相邻三列，起点终点都不固定
1289. 下降路径最小和 II	困难	禁止同列，需预存上一行的最小与次小做 $O(1)$ 转移
1301. 最大得分的路径数目	困难	极值与方案数两张表同步推进，并列时要合并计数
LCR 098. 不同路径	中等	与 62 同题，适合练滚动数组压到一维
LCR 099. 最小路径和	中等	与 64 同题，可原地改写 grid 省掉额外空间
LCR 100. 三角形最小路径和	中等	与 120 同题，一维数组需倒序更新避免覆盖
剑指 Offer 47. 礼物的最大价值	中等	求最大和且全为非负，是本题去掉负数后的简化版