LeetCode 1594. 矩阵的最大非负积
题目描述
题意分析
从矩阵左上角出发，每次只能向右或向下移动，直到右下角。每条路径的得分是经过的所有格子值的乘积，包含起点和终点。
在所有非负得分中找最大值，最后对 $10^9+7$ 取模；如果全部路径乘积都为负，返回
-1。零属于非负结果，不能当成失败。矩阵含负数，选取局部最大乘积不一定能得到终点最大值。
解法：最大最小乘积动态规划
核心思路
[!blue]
一个格子的前一步只能来自上方或左方。若当前格为正数，原乘积越大，乘完仍越大；若为负数，大小关系反转，原来最小的乘积可能变成新的最大值；若为零，所有路径乘积都归零。
因此每格同时保存两种状态：
maxDp[i][j]为到达这里的最大真实乘积，minDp[i][j]为最小真实乘积。上、左两个来源各有最大与最小，分别乘当前值后得到四个候选，取它们的最大、最小作为当前状态。为什么不保存所有可能乘积？乘以一个固定数时，函数要么保序、要么逆序、要么恒为零，其最大和最小输出一定来自输入的某个极值。每个前驱只保留两端已经足够，不会漏掉当前极值；向后逐格沿用这一性质即可。
起点只有自身一个乘积。第一行和第一列都只有唯一到达路径，两种状态相同，沿唯一方向累乘初始化；随后按行列顺序处理内部格子，所需上方与左方状态均已完成。
状态必须保留真实乘积，不能途中取模，因为模运算会改变大小关系。题目路径最多经过 29 个格子，每格绝对值不超过四，绝对乘积不超过 $4^{29}$，64 位整数可保存。最后查看终点最大值：负数表示没有非负路径，否则再取模返回。
解题步骤
- 创建最大、最小乘积表，起点都设为起点值。
- 沿第一列、第一行累乘，初始化唯一到达路径。
- 对内部格子，计算上方与左方两种极值乘当前值的四个候选。
- 分别取最大值和最小值填入当前状态。
- 终点最大值小于零则返回
-1，否则对规定模数取余。
代码实现
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)$，每格只比较固定数量的候选。
- 空间复杂度：$O(mn)$，保存两张乘积状态表。
关键点总结
[!green]
- 负数会交换极值角色，最大值和最小值必须同时保留。
- 固定乘数只会保序、逆序或归零，两个极值足以支持后续转移。
- 唯一路径的边界先初始化，避免把默认零当成实际可达乘积。
- 先判断真实最优乘积是否非负，最后才取模。
易错点总结
[!yellow]
- 只保存最大值，会丢掉遇到负数后最有利的最小前驱。
- 中途取模会破坏极值比较，不能用模后值决定路径优劣。
- 把终点最大值等于零也判为失败，会漏掉合法零乘积路径。
- 状态用 32 位整数容易在连续相乘时溢出，要从乘法开始就使用宽整数。
- 起点必须用格子本身初始化，不能无条件设为一或零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 152. 乘积最大子数组 | 中等 | 负数会让最大最小乘积交换角色，因此每个状态都需同时保留最大与最小值。 |
| 64. 最小路径和 | 中等 | 同样从左或上方转移，本题累乘且存在负数，不能只保留一个最优前驱值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！