# 1594. Maximum Non Negative Product in a Matrix

• Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public: int maxProductPath(vector>& grid) { constexpr int kMod = 1'000'000'007; const int m = grid.size(); const int n = grid[0].size(); // dpMin[i][j] := the min product from (0, 0) to (i, j) // dpMax[i][j] := the max product from (0, 0) to (i, j) vector> dpMin(m, vector(n)); vector> dpMax(m, vector(n)); dpMin[0][0] = dpMax[0][0] = grid[0][0]; for (int i = 1; i < m; ++i) dpMin[i][0] = dpMax[i][0] = dpMin[i - 1][0] * grid[i][0]; for (int j = 1; j < n; ++j) dpMin[0][j] = dpMax[0][j] = dpMin[0][j - 1] * grid[0][j]; for (int i = 1; i < m; ++i) for (int j = 1; j < n; ++j) if (grid[i][j] < 0) { dpMin[i][j] = max(dpMax[i - 1][j], dpMax[i][j - 1]) * grid[i][j]; dpMax[i][j] = min(dpMin[i - 1][j], dpMin[i][j - 1]) * grid[i][j]; } else { dpMin[i][j] = min(dpMin[i - 1][j], dpMin[i][j - 1]) * grid[i][j]; dpMax[i][j] = max(dpMax[i - 1][j], dpMax[i][j - 1]) * grid[i][j]; } const long maxi = max(dpMin.back().back(), dpMax.back().back()); return maxi < 0 ? -1 : maxi % kMod; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public int maxProductPath(int[][] grid) { final int kMod = 1_000_000_007; final int m = grid.length; final int n = grid[0].length; // dpMin[i][j] := the min product from (0, 0) to (i, j) // dpMax[i][j] := the max product from (0, 0) to (i, j) long[][] dpMin = new long[m][n]; long[][] dpMax = new long[m][n]; dpMin[0][0] = dpMax[0][0] = grid[0][0]; for (int i = 1; i < m; ++i) dpMin[i][0] = dpMax[i][0] = dpMin[i - 1][0] * grid[i][0]; for (int j = 1; j < n; ++j) dpMin[0][j] = dpMax[0][j] = dpMin[0][j - 1] * grid[0][j]; for (int i = 1; i < m; ++i) for (int j = 1; j < n; ++j) if (grid[i][j] < 0) { dpMin[i][j] = Math.max(dpMax[i - 1][j], dpMax[i][j - 1]) * grid[i][j]; dpMax[i][j] = Math.min(dpMin[i - 1][j], dpMin[i][j - 1]) * grid[i][j]; } else { dpMin[i][j] = Math.min(dpMin[i - 1][j], dpMin[i][j - 1]) * grid[i][j]; dpMax[i][j] = Math.max(dpMax[i - 1][j], dpMax[i][j - 1]) * grid[i][j]; } final long max = Math.max(dpMin[m - 1][n - 1], dpMax[m - 1][n - 1]); return max < 0 ? -1 : (int) (max % kMod); } }