1594.矩阵的最大非负积：动态规划O(mn)

【LetMeFly】1594.矩阵的最大非负积：动态规划O(mn)

力扣题目链接：https://leetcode.cn/problems/maximum-non-negative-product-in-a-matrix/

给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中 向右 或 向下 移动。

在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 109 + 7 取余 的结果。如果最大积为 负数 ，则返回 -1 。

注意，取余是在得到最大积之后执行的。

 

示例 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)

示例 3：

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

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 15
• -4 <= grid[i][j] <= 4

解题方法：动态规划

使用两个和grid等大的数组实时记录下每个位置的最大最小值就好了。

• 如果$grid[i][j]\geq 0$，则：

  • $maximum[i][j] = \max(left, up)\times grid[i][j]$
  • $minimum[i][j] = \min(left,up)\times grid[i][j]$

• 如果$grd[i][j]\lt 0$，则：

  • $maximum[i][j] = \min(left, up)\times grid[i][j]$
  • $minimum[i][j] = \max(left, up)\times grid[i][j]$

以上。

• 时间复杂度$O(N^2)$
• 空间复杂度$O(N\log N)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-23 22:00:02
 */
typedef long long ll;
const ll MOD = 1e9 + 7;
class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<ll>> maximum(n, vector<ll>(m));
        vector<vector<ll>> minimum(n, vector<ll>(m));

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

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (grid[i][j] >= 0) {
                    maximum[i][j] = max(maximum[i][j - 1], maximum[i - 1][j]) * grid[i][j];
                    minimum[i][j] = min(minimum[i][j - 1], minimum[i - 1][j]) * grid[i][j];
                } else {
                    maximum[i][j] = min(minimum[i][j - 1], minimum[i - 1][j]) * grid[i][j];
                    minimum[i][j] = max(maximum[i][j - 1], maximum[i - 1][j]) * grid[i][j];
                }
            }
        }

        return maximum[n - 1][m - 1] >= 0 ? maximum[n - 1][m - 1] % MOD : -1;
    }
};

#ifdef _DEBUG
/*
[[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]

之前的逻辑：
ll left_max = j ? maximum[i][j - 1] : 1;
ll left_min = j ? minimum[i][j - 1] : 1;
ll up_max = i ? maximum[i - 1][j] : 1;
ll up_min = i ? minimum[i - 1][j] : 1;
minimum[i][j] = max(left_max, up_max) * grid[i][j];  // when grid[i][j] < 0
错在：
-1 -2
在-2时候，min和max都应该是2，但是max(-1, 1)会导致计算结果为-2。

-1
*/
int main() {
    string s;
    while (cin >> s) {
        Solution sol;
        vector<vector<int>> v = stringToVectorVector(s);
        cout << sol.maxProductPath(v) << endl;
    }
    return 0;
}
#endif

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源