LeetCode 1594: Maximum Non Negative Product in a Matrix
Problem Description
Explanation
To solve this problem, we can use dynamic programming. We will maintain two arrays to keep track of the maximum positive product and the minimum negative product that can be obtained at each cell. At each cell, we update these values based on the values obtained from moving either from the cell above or the cell to the left.
- Initialize two 2D arrays
maxProdandminProdof sizem x nto store the maximum positive product and the minimum negative product. - Initialize
maxProd[0][0] = minProd[0][0] = grid[0][0]. - Iterate through the matrix starting from
(0, 1)and(1, 0). - Update
maxProd[i][j]andminProd[i][j]based on the values from the cell above and the cell to the left. - Return the maximum non-negative product modulo 10^9 + 7.
Time complexity: O(m * n) Space complexity: O(m * n)
Solutions
class Solution {
public int maxProductPath(int[][] grid) {
int m = grid.length, n = grid[0].length;
long[][] maxProd = new long[m][n];
long[][] minProd = new long[m][n];
maxProd[0][0] = minProd[0][0] = grid[0][0];
// Fill the first row
for (int j = 1; j < n; j++) {
maxProd[0][j] = minProd[0][j] = maxProd[0][j - 1] * grid[0][j];
}
// Fill the first column
for (int i = 1; i < m; i++) {
maxProd[i][0] = minProd[i][0] = maxProd[i - 1][0] * grid[i][0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (grid[i][j] >= 0) {
maxProd[i][j] = Math.max(maxProd[i - 1][j], maxProd[i][j - 1]) * grid[i][j];
minProd[i][j] = Math.min(minProd[i - 1][j], minProd[i][j - 1]) * grid[i][j];
} else {
maxProd[i][j] = Math.min(minProd[i - 1][j], minProd[i][j - 1]) * grid[i][j];
minProd[i][j] = Math.max(maxProd[i - 1][j], maxProd[i][j - 1]) * grid[i][j];
}
}
}
long result = maxProd[m - 1][n - 1] % 1000000007;
return result < 0 ? -1 : (int)result;
}
}Loading editor...