#leetcode #medium #google 1594. Maximum Non Negative Product in a Matrix Дейлик литкода 23.03.2026 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. Лень чет этот дп пояснять. (как и делать) class Solution { public int maxProductPath(int[][] grid) { final int MOD = 1000000000 + 7; int m = grid.length; int n = grid[0].length; long[][] maxgt = new long[m][n]; long[][] minlt = new long[m][n]; maxgt[0][0] = minlt[0][0] = grid[0][0]; for (int i = 1; i < n; i++) { maxgt[0][i] = minlt[0][i] = maxgt[0][i - 1] grid[0][i]; } for (int i = 1; i < m; i++) { maxgt[i][0] = minlt[i][0] = maxgt[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) { maxgt[i][j] = Math.max(maxgt[i][j - 1], maxgt[i - 1][j]) grid[i][j]; minlt[i][j] = Math.min(minlt[i][j - 1], minlt[i - 1][j]) grid[i][j]; } else { maxgt[i][j] = Math.min(minlt[i][j - 1], minlt[i - 1][j]) grid[i][j]; minlt[i][j] = Math.max(maxgt[i][j - 1], maxgt[i - 1][j]) grid[i][j]; } } } if (maxgt[m - 1][n - 1] < 0) { return -1; } else { return (int) (maxgt[m - 1][n - 1] % MOD); } } }