Maximum Non Negative Product in a Matrix LeetCode solution in C++

1
const long long MOD = 1e9 + 7;
2
class Solution {
3
 public:
4
  int maxProductPath(vector<vector<int>> &grid) {
5
    long long mx[20][20] = {0};
6
    long long mn[20][20] = {0};
7
    int row = grid.size(), col = grid[0].size();
8

9
    // Init
10
    mx[0][0] = mn[0][0] = grid[0][0];
11

12
    // Init the row0 and col0 to be the continuous multiply of the elements.
13
    for (int i = 1; i < row; i++) {
14
      mx[i][0] = mn[i][0] = mx[i - 1][0] * grid[i][0];
15
    }
16
    for (int j = 1; j < col; j++) {
17
      mx[0][j] = mn[0][j] = mx[0][j - 1] * grid[0][j];
18
    }
19

20
    // DP as the explanation picture shows
21
    for (int i = 1; i < row; i++) {
22
      for (int j = 1; j < col; j++) {
23
        mx[i][j] = max(max(mx[i - 1][j], mx[i][j - 1]) * grid[i][j],
24
                       min(mn[i - 1][j], mn[i][j - 1]) * grid[i][j]);
25
        mn[i][j] = min(max(mx[i - 1][j], mx[i][j - 1]) * grid[i][j],
26
                       min(mn[i - 1][j], mn[i][j - 1]) * grid[i][j]);
27
      }
28
    }
29

30
    return mx[row - 1][col - 1] < 0 ? -1 : mx[row - 1][col - 1] % MOD;
31
  }
32
};