Formatted question description: https://leetcode.ca/all/1594.html

# 1594. Maximum Non Negative Product in a Matrix (Medium)

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 + 7If the maximum product is negative return -1.

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

Example 1:

Input: grid = [[-1,-2,-3],
[-2,-3,-3],
[-3,-3,-2]]
Output: -1
Explanation: It's not possible to get non-negative product in the path from (0, 0) to (2, 2), so return -1.


Example 2:

Input: grid = [[1,-2,1],
[1,-2,1],
[3,-4,1]]
Output: 8
Explanation: Maximum non-negative product is in bold (1 * 1 * -2 * -4 * 1 = 8).


Example 3:

Input: grid = [[1, 3],
[0,-4]]
Output: 0
Explanation: Maximum non-negative product is in bold (1 * 0 * -4 = 0).


Example 4:

Input: grid = [[ 1, 4,4,0],
[-2, 0,0,1],
[ 1,-1,1,1]]
Output: 2
Explanation: Maximum non-negative product is in bold (1 * -2 * 1 * -1 * 1 * 1 = 2).


Constraints:

• 1 <= rows, cols <= 15
• -4 <= grid[i][j] <= 4

Related Topics:
Dynamic Programming, Greedy

## Solution 1. DP

// OJ: https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/

// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int maxProductPath(vector<vector<int>>& G) {
long ans = 0, mod = 1e9+7, M = G.size(), N = G.size();
vector<vector<pair<long, long>>> dp(M + 1, vector<pair<long, long>>(N + 1, { INT_MAX, INT_MIN })); // min, max
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (i == 0 && j == 0) dp[i][j] =  {G[i][j], G[i][j]};
if (i != 0) {
dp[i][j].first = min(dp[i - 1][j].first * G[i][j], dp[i - 1][j].second * G[i][j]);
dp[i][j].second = max(dp[i - 1][j].first * G[i][j], dp[i - 1][j].second * G[i][j]);
}
if (j != 0) {
dp[i][j].first = min({ dp[i][j].first, dp[i][j - 1].first * G[i][j], dp[i][j - 1].second * G[i][j] });
dp[i][j].second = max({ dp[i][j].second, dp[i][j - 1].first * G[i][j], dp[i][j - 1].second * G[i][j] });
}
}
}
return dp[M - 1][N - 1].second < 0 ? -1 : (dp[M - 1][N - 1].second % mod);
}
};


## Solution 2. DP with Space Optimization

// OJ: https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/

// Time: O(MN)
// Space: O(N)
class Solution {
public:
int maxProductPath(vector<vector<int>>& G) {
long ans = 0, mod = 1e9+7, M = G.size(), N = G.size();
vector<pair<long, long>> dp(N + 1); // min, max
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
long mn = INT_MAX, mx = INT_MIN;
if (i == 0 && j == 0) mn = mx = G[i][j];
if (i != 0) {
mn = min(dp[j].first * G[i][j], dp[j].second * G[i][j]);
mx = max(dp[j].first * G[i][j], dp[j].second * G[i][j]);
}
if (j != 0) {
mn = min({ mn, dp[j - 1].first * G[i][j], dp[j - 1].second * G[i][j] });
mx = max({ mx, dp[j - 1].first * G[i][j], dp[j - 1].second * G[i][j] });
}
dp[j] = { mn, mx };
}
}
return dp[N - 1].second < 0 ? -1 : (dp[N - 1].second % mod);
}
};


Java

class Solution {
public int maxProductPath(int[][] grid) {
final int MODULO = 1000000007;
long maxProduct = -1;
int rows = grid.length, columns = grid.length;
long[][][] products = new long[rows][columns];
products = products = grid;
for (int i = 1; i < rows; i++) {
long product = products[i - 1] * grid[i];
if (product == 0 && maxProduct < 0)
maxProduct = 0;
products[i] = products[i] = product;
}
for (int j = 1; j < columns; j++) {
long product = products[j - 1] * grid[j];
if (product == 0 && maxProduct < 0)
maxProduct = 0;
products[j] = products[j] = product;
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
int num = grid[i][j];
if (num == 0 && maxProduct < 0)
maxProduct = 0;
long product1 = products[i - 1][j] * num;
long product2 = products[i - 1][j] * num;
long product3 = products[i][j - 1] * num;
long product4 = products[i][j - 1] * num;
long[] array = {product1, product2, product3, product4};
Arrays.sort(array);
long min = array, max = array;
if (max > 0)
products[i][j] = max;
else
products[i][j] = min;
if (min < 0)
products[i][j] = min;
else
products[i][j] = max;
}
}
maxProduct = Math.max(maxProduct, Math.max(products[rows - 1][columns - 1], products[rows - 1][columns - 1]));
return (int) (maxProduct % MODULO);
}
}