Welcome to Subscribe On Youtube
1594. Maximum Non Negative Product in a Matrix
Description
You are given a m x n 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 (m - 1, n - 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.
Example 1:
Input: grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]] Output: -1 Explanation: It is 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 shown (1 * 1 * -2 * -4 * 1 = 8).
Example 3:
Input: grid = [[1,3],[0,-4]] Output: 0 Explanation: Maximum non-negative product is shown (1 * 0 * -4 = 0).
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 15-4 <= grid[i][j] <= 4
Solutions
-
class Solution { private static final int MOD = (int) 1e9 + 7; public int maxProductPath(int[][] grid) { int m = grid.length; int n = grid[0].length; long[][][] dp = new long[m][n][2]; dp[0][0][0] = grid[0][0]; dp[0][0][1] = grid[0][0]; for (int i = 1; i < m; ++i) { dp[i][0][0] = dp[i - 1][0][0] * grid[i][0]; dp[i][0][1] = dp[i - 1][0][1] * grid[i][0]; } for (int j = 1; j < n; ++j) { dp[0][j][0] = dp[0][j - 1][0] * grid[0][j]; dp[0][j][1] = dp[0][j - 1][1] * grid[0][j]; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { int v = grid[i][j]; if (v >= 0) { dp[i][j][0] = Math.min(dp[i - 1][j][0], dp[i][j - 1][0]) * v; dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) * v; } else { dp[i][j][0] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) * v; dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i][j - 1][0]) * v; } } } long ans = dp[m - 1][n - 1][1]; return ans < 0 ? -1 : (int) (ans % MOD); } } -
using ll = long long; const int mod = 1e9 + 7; class Solution { public: int maxProductPath(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<vector<ll>>> dp(m, vector<vector<ll>>(n, vector<ll>(2, grid[0][0]))); for (int i = 1; i < m; ++i) { dp[i][0][0] = dp[i - 1][0][0] * grid[i][0]; dp[i][0][1] = dp[i - 1][0][1] * grid[i][0]; } for (int j = 1; j < n; ++j) { dp[0][j][0] = dp[0][j - 1][0] * grid[0][j]; dp[0][j][1] = dp[0][j - 1][1] * grid[0][j]; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { int v = grid[i][j]; if (v >= 0) { dp[i][j][0] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * v; dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * v; } else { dp[i][j][0] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * v; dp[i][j][1] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * v; } } } ll ans = dp[m - 1][n - 1][1]; return ans < 0 ? -1 : (int) (ans % mod); } }; -
class Solution: def maxProductPath(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) mod = 10**9 + 7 dp = [[[grid[0][0]] * 2 for _ in range(n)] for _ in range(m)] for i in range(1, m): dp[i][0] = [dp[i - 1][0][0] * grid[i][0]] * 2 for j in range(1, n): dp[0][j] = [dp[0][j - 1][0] * grid[0][j]] * 2 for i in range(1, m): for j in range(1, n): v = grid[i][j] if v >= 0: dp[i][j][0] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * v dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * v else: dp[i][j][0] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * v dp[i][j][1] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * v ans = dp[-1][-1][1] return -1 if ans < 0 else ans % mod -
func maxProductPath(grid [][]int) int { m, n := len(grid), len(grid[0]) dp := make([][][]int, m) for i := range dp { dp[i] = make([][]int, n) for j := range dp[i] { dp[i][j] = make([]int, 2) } } dp[0][0] = []int{grid[0][0], grid[0][0]} for i := 1; i < m; i++ { dp[i][0][0] = dp[i-1][0][0] * grid[i][0] dp[i][0][1] = dp[i-1][0][1] * grid[i][0] } for j := 1; j < n; j++ { dp[0][j][0] = dp[0][j-1][0] * grid[0][j] dp[0][j][1] = dp[0][j-1][1] * grid[0][j] } for i := 1; i < m; i++ { for j := 1; j < n; j++ { v := grid[i][j] if v >= 0 { dp[i][j][0] = min(dp[i-1][j][0], dp[i][j-1][0]) * v dp[i][j][1] = max(dp[i-1][j][1], dp[i][j-1][1]) * v } else { dp[i][j][0] = max(dp[i-1][j][1], dp[i][j-1][1]) * v dp[i][j][1] = min(dp[i-1][j][0], dp[i][j-1][0]) * v } } } ans := dp[m-1][n-1][1] if ans < 0 { return -1 } var mod int = 1e9 + 7 return ans % mod } -
function maxProductPath(grid: number[][]): number { const m = grid.length, n = grid[0].length; const f = Array.from({ length: m }, () => Array.from({ length: n }, () => [0, 0])); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { const x = grid[i][j]; if (i === 0 && j === 0) { f[i][j] = [x, x]; continue; } let mn = Infinity, mx = -Infinity; if (i > 0) { const [a, b] = f[i - 1][j]; mn = Math.min(mn, a * x, b * x); mx = Math.max(mx, a * x, b * x); } if (j > 0) { const [a, b] = f[i][j - 1]; mn = Math.min(mn, a * x, b * x); mx = Math.max(mx, a * x, b * x); } f[i][j] = [mn, mx]; } } const ans = f[m - 1][n - 1][1]; const mod = 1e9 + 7; return ans < 0 ? -1 : ans % mod; } -
impl Solution { pub fn max_product_path(grid: Vec<Vec<i32>>) -> i32 { let m = grid.len(); let n = grid[0].len(); let mut f = vec![vec![[0i64; 2]; n]; m]; for i in 0..m { for j in 0..n { let x = grid[i][j] as i64; if i == 0 && j == 0 { f[i][j] = [x, x]; continue; } let mut mn = i64::MAX; let mut mx = i64::MIN; if i > 0 { let [a, b] = f[i - 1][j]; mn = mn.min(a * x).min(b * x); mx = mx.max(a * x).max(b * x); } if j > 0 { let [a, b] = f[i][j - 1]; mn = mn.min(a * x).min(b * x); mx = mx.max(a * x).max(b * x); } f[i][j] = [mn, mx]; } } let ans = f[m - 1][n - 1][1]; let mod_val = 1_000_000_007i64; if ans < 0 { -1 } else { (ans % mod_val) as i32 } } }