commit ead16e7f28af79f4c3595db5c98d9fcadef102b6
parent 072eb6c9c8b79bafb9b8ce61106debfb0b58ffeb
Author: Jack Sangdahl <jack@pngu.org>
Date: Sun, 22 Mar 2026 22:12:38 -0600
1594. maximum non negative product in a matrix
Diffstat:
2 files changed, 126 insertions(+), 0 deletions(-)
diff --git a/max_non_neg_prod_mat.c b/max_non_neg_prod_mat.c
@@ -0,0 +1,79 @@
+// 1594. Maximum Non Negative Product in a Matrix
+#include "leetcode.h"
+
+/*
+ * you are given an '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 and ending
+ * in the bottom-right corner, 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. if the
+ * maximum product is negative, return -1. notice that the modulo is performed
+ * after getting the maximum product.
+ */
+
+int maxProductPath(int **grid, int gridSize, int *gridColSize) {
+ int m = gridSize, n = gridColSize[0], mod = 1e9 + 7;
+ long long **min = (long long **)malloc(m * sizeof(long long *));
+ long long **max = (long long **)malloc(m * sizeof(long long *));
+ for (int i = 0; i < m; i++) {
+ min[i] = (long long *)malloc(n * sizeof(long long));
+ max[i] = (long long *)malloc(n * sizeof(long long));
+ for (int j = 0; j < n; j++)
+ min[i][j] = max[i][j] = LLONG_MAX;
+ }
+ min[0][0] = max[0][0] = grid[0][0];
+ for (int i = 0; i < m; i++) {
+ for (int j = 0; j < n; j++) {
+ if (!i && !j)
+ continue;
+ long long mn = LLONG_MAX, mx = LLONG_MIN;
+ if (i > 0) {
+ long long a = min[i - 1][j] * grid[i][j];
+ long long b = max[i - 1][j] * grid[i][j];
+ mn = fmin(a, fmin(b, mn));
+ mx = fmax(a, fmax(b, mx));
+ }
+ if (j > 0) {
+ long long a = min[i][j - 1] * grid[i][j];
+ long long b = max[i][j - 1] * grid[i][j];
+ mn = fmin(a, fmin(b, mn));
+ mx = fmax(a, fmax(b, mx));
+ }
+ min[i][j] = mn;
+ max[i][j] = mx;
+ }
+ }
+ long long ans = max[m - 1][n - 1];
+ for (int i = 0; i < m; i++) {
+ free(min[i]);
+ free(max[i]);
+ }
+ free(min);
+ free(max);
+ return ans >= 0 ? ans % mod : -1;
+}
+
+int main() {
+ int g1i[3][3] = {{-1, -2, -3}, {-2, -3, -3}, {-3, -3, -2}};
+ int g2i[3][3] = {{1, -2, 1}, {1, -2, 1}, {3, -4, 1}};
+ int g3i[2][2] = {{1, 3}, {0, -4}};
+ struct two_d_arr *g1 =
+ two_d_arr_init(ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ struct two_d_arr *g2 =
+ two_d_arr_init(ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ struct two_d_arr *g3 =
+ two_d_arr_init(ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i);
+ int r1 = maxProductPath(g1->arr, g1->row_size, g1->col_size);
+ int r2 = maxProductPath(g2->arr, g2->row_size, g2->col_size);
+ int r3 = maxProductPath(g3->arr, g3->row_size, g3->col_size);
+ printf("%d\n", r1);
+ assert(r1 == -1);
+ printf("%d\n", r2);
+ assert(r2 == 8);
+ printf("%d\n", r3);
+ assert(r3 == 0);
+ two_d_arr_free(g1);
+ two_d_arr_free(g2);
+ two_d_arr_free(g3);
+}
diff --git a/max_non_neg_prod_mat.py b/max_non_neg_prod_mat.py
@@ -0,0 +1,47 @@
+# 1594. mximum Non Negative Product in a Matrix
+from typing import List
+
+"""
+you are given an '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 and ending
+in the bottom-right corner, 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. if the
+maximum product is negative, return -1. notice that the modulo is performed
+after getting the maximum product.
+"""
+
+
+class Solution:
+ def maxProductPath(self, grid: List[List[int]]) -> int:
+ m, n = len(grid), len(grid[0])
+ mod = 10**9 + 7
+ mn = [[float("inf")] * n for _ in range(m)]
+ mx = [[float("-inf")] * n for _ in range(m)]
+ mn[0][0], mx[0][0] = grid[0][0], grid[0][0]
+ for i in range(m):
+ for j in range(n):
+ if i == 0 and j == 0:
+ continue
+ mn[i][j] = min(
+ mn[i - 1][j] * grid[i][j] if i > 0 else float("inf"),
+ mx[i - 1][j] * grid[i][j] if i > 0 else float("inf"),
+ mn[i][j - 1] * grid[i][j] if j > 0 else float("inf"),
+ mx[i][j - 1] * grid[i][j] if j > 0 else float("inf"),
+ )
+ mx[i][j] = max(
+ mn[i - 1][j] * grid[i][j] if i > 0 else float("-inf"),
+ mx[i - 1][j] * grid[i][j] if i > 0 else float("-inf"),
+ mn[i][j - 1] * grid[i][j] if j > 0 else float("-inf"),
+ mx[i][j - 1] * grid[i][j] if j > 0 else float("-inf"),
+ )
+ ans = mx[-1][-1]
+ return ans % mod if ans >= 0 else -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxProductPath(grid=[[-1, -2, -3], [-2, -3, -3], [-3, -3, -2]]))
+ print(obj.maxProductPath(grid=[[1, -2, 1], [1, -2, 1], [3, -4, 1]]))
+ print(obj.maxProductPath(grid=[[1, 3], [0, -4]]))
