leetcode1594.矩阵的最大非负积

题目如下

数据范围 示例

本题难就难在矩阵存在负数，我们可以先思考如果矩阵每个数都大于等于0那么很简单我们只需要维护左边和上面的最大值即可。那么如果遇到负数显然要得到最大值就要和左边和右边的最小值相乘。所以这里我们维护两个二维数组用于存从(0,0)开始到(i,j)的最大值和最小值。

通过代码

class Solution { public: int maxProductPath(vector<vector<int>>& grid) { int n = grid.size(); int m = grid[0].size(); int mod = 1e9 + 7; vector<vector<long long>> dp1(n, vector<long long>(m)); vector<vector<long long>> dp2(n, vector<long long>(m)); dp1[0][0] = dp2[0][0] = grid[0][0]; for (int i = 1; i < n; i++) { dp1[i][0] = dp2[i][0] = grid[i][0] * dp1[i - 1][0]; } for (int i = 1; i < m; i++) { dp1[0][i] = dp2[0][i] = grid[0][i] * dp1[0][i - 1]; } for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (grid[i][j] >= 0) { dp1[i][j] = max(dp1[i - 1][j], dp1[i][j - 1]) * grid[i][j]; dp2[i][j] = min(dp2[i - 1][j], dp2[i][j - 1]) * grid[i][j]; } else { dp1[i][j] = min(dp2[i - 1][j], dp2[i][j - 1]) * grid[i][j]; dp2[i][j] = max(dp1[i - 1][j], dp1[i][j - 1]) * grid[i][j]; } } } if (dp1[n - 1][m - 1] < 0) return -1; return dp1[n - 1][m - 1] % mod; } };

利用滚动数组思想优化后的代码

class Solution { public: int maxProductPath(vector<vector<int>>& grid) { int n = grid.size(); int m = grid[0].size(); int mod = 1e9 + 7; vector<long long> dp1(m); vector<long long> dp2(m); long long t1, t2; dp1[0] = dp2[0] = grid[0][0]; for (int i = 1; i < m; i++) { dp1[i] = dp2[i] = grid[0][i] * dp1[i - 1]; } for (int i = 1; i < n; i++) { dp1[0] = dp2[0] = dp1[0] * grid[i][0]; for (int j = 1; j < m; j++) { if (grid[i][j] >= 0) { dp1[j] = max(dp1[j - 1], dp1[j]) * grid[i][j]; dp2[j] = min(dp2[j - 1], dp2[j]) * grid[i][j]; } else { t1 = max(dp1[j - 1], dp1[j]); t2 = min(dp2[j - 1], dp2[j]); dp1[j] = t2 * grid[i][j]; dp2[j] = t1 * grid[i][j]; } } } if (dp1[m - 1] < 0) return -1; return dp1[m - 1] % mod; } };