Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 1594. Maximum Non Negative Product in a Matrix

---

參考資訊：
https://algo.monster/liteproblems/1594

題目：


方法：

Dynamic Programming

解答：

class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        using ll = long long;
        const int MOD = 1e9 + 7;

        int row_size = grid.size();
        int col_size = grid[0].size();
        vector<vector<ll>> q_min(row_size, vector<ll>(col_size, 0));
        vector<vector<ll>> q_max(row_size, vector<ll>(col_size, 0));

        q_min[0][0] = grid[0][0];
        q_max[0][0] = grid[0][0];
        for (int i = 1; i < row_size; ++i) {
            q_min[i][0] = q_min[i - 1][0] * grid[i][0];
            q_max[i][0] = q_max[i - 1][0] * grid[i][0];
        }

        for (int j = 1; j < col_size; ++j) {
            q_min[0][j] = q_min[0][j - 1] * grid[0][j];
            q_max[0][j] = q_max[0][j - 1] * grid[0][j];
        }

        for (int i = 1; i < row_size; ++i) {
            for (int j = 1; j < col_size; ++j) {
                ll v = grid[i][j];

                if (v >= 0) {
                    q_min[i][j] = min(q_min[i - 1][j], q_min[i][j - 1]) * v;
                    q_max[i][j] = max(q_max[i - 1][j], q_max[i][j - 1]) * v;
                }
                else {
                    q_min[i][j] = max(q_max[i - 1][j], q_max[i][j - 1]) * v;
                    q_max[i][j] = min(q_min[i - 1][j], q_min[i][j - 1]) * v;
                }
            }
        }

        ll r = q_max[row_size - 1][col_size - 1];
        return r < 0 ? -1 : static_cast<int>(r % MOD);
    }
};