Skip to content

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<vector<int>>& grid) {
    constexpr int kMod = 1'000'000'007;
    const int m = grid.size();
    const int n = grid[0].size();
    // dpMin[i][j] := the minimum product from (0, 0) to (i, j)
    // dpMax[i][j] := the maximum product from (0, 0) to (i, j)
    vector<vector<long>> dpMin(m, vector<long>(n));
    vector<vector<long>> dpMax(m, vector<long>(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 mx = max(dpMin.back().back(), dpMax.back().back());
    return mx < 0 ? -1 : mx % 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 minimum product from (0, 0) to (i, j)
    // dpMax[i][j] := the maximum 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 mx = Math.max(dpMin[m - 1][n - 1], dpMax[m - 1][n - 1]);
    return mx < 0 ? -1 : (int) (mx % kMod);
  }
}