Steward

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

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

---

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

題目：


方法：

Dynamic Programming

解答：

typedef long long ll;

ll min(ll a, ll b)
{
    return a > b ? b : a;
}

ll max(ll a, ll b)
{
    return a > b ? a : b;
}

int maxProductPath(int** grid, int gridSize, int* gridColSize)
{
    const int MOD = 1e9 + 7;

    ll r = 0;
    int i = 0;
    int j = 0;
    int row_size = gridSize;
    int col_size = gridColSize[0];
    ll **q_min = calloc(row_size, sizeof(ll *));
    ll **q_max = calloc(row_size, sizeof(ll *));

    for (i = 0; i < row_size; i++) {
        q_min[i] = calloc(col_size, sizeof(ll));
        q_max[i] = calloc(col_size, sizeof(ll));
    }

    q_min[0][0] = grid[0][0];
    q_max[0][0] = grid[0][0];
    for (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 (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 (i = 1; i < row_size; i++) {
        for (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;
            }
        }
    }

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