1594. Maximum Non Negative Product in a Matrix

You are given a rows x cols matrix grid. Initially, you are located at the top-left corner (0, 0), and in each step, you can only move right or down in the matrix.

Among all possible paths starting from the top-left corner (0, 0) and ending in the bottom-right corner (rows - 1, cols - 1), find the path with the maximum non-negative product. The product of a path is the product of all integers in the grid cells visited along the path.

Return the maximum non-negative product modulo 109 + 7. If the maximum product is negative return -1.

Notice that the modulo is performed after getting the maximum product.

class Solution {
public:
    int maxProductPath(vector<vector<int>>& grid) {
        int cols{(int)grid[0].size()}, rows{(int)grid.size()}, mod = 1e9 + 7;
        pair<long, long> dp[15][15];
        dp[0][0].first = dp[0][0].second = grid[0][0];
        for(int i = 1; i < rows; i++) {
            dp[i][0].first = dp[i][0].second = dp[i - 1][0].first * grid[i][0];
        }

        for(int i = 1; i < cols; i++) {
            dp[0][i].first = dp[0][i].second = dp[0][i - 1].first * grid[0][i];
        }
        
        for(int i = 1; i < rows; i++) {
            for(int j = 1; j < cols; j++) {
                dp[i][j].first = (grid[i][j] < 0 ? min(dp[i - 1][j].second, dp[i][j - 1].second) : max(dp[i - 1][j].first, dp[i][j - 1].first))  * grid[i][j];
                dp[i][j].second = (grid[i][j] < 0 ? max(dp[i - 1][j].first, dp[i][j - 1].first) : min(dp[i-1][j].second, dp[i][j - 1].second)) * grid[i][j];
            }
        }
        return max((long)-1, dp[rows - 1][cols - 1].first) % mod;
    }
};