How do I manage negative numbers in the Maximum Non Negative Product in a Matrix problem?

By maintaining both the maximum and minimum products at each cell, you can properly handle negative numbers that may flip the sign of the product.

What is the time complexity of solving the Maximum Non Negative Product in a Matrix problem?

The time complexity is O(m * n), where m and n are the number of rows and columns in the matrix.

Why do I need to track both max and min products in this problem?

Tracking both allows you to properly handle negative numbers, as multiplying by a negative can turn the minimum product into a maximum one.

What happens if the product becomes negative at any point in the grid?

If the product is negative and no non-negative product path is possible, the function will return -1.

What is the purpose of the modulo operation in this problem?

The modulo operation ensures that large product values are reduced within the range of 10^9 + 7, as required by the problem's constraints.

#1594

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

矩阵的最大非负积

给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中向右或向下移动。在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有最大非负积的路径。路径的积是沿路径访问的单元格中所有整数的乘积。返…

数组动态规划矩阵

题目描述

给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中向右或向下移动。

在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 10⁹ + 7 取余的结果。如果最大积为负数，则返回 -1 。

注意，取余是在得到最大积之后执行的。

示例 1：

输入：grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
输出：-1
解释：从 (0, 0) 到 (2, 2) 的路径中无法得到非负积，所以返回 -1 。

示例 2：

输入：grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
输出：8
解释：最大非负积对应的路径如图所示 (1 * 1 * -2 * -4 * 1 = 8)

示例 3：

输入：grid = [[1,3],[0,-4]]
输出：0
解释：最大非负积对应的路径如图所示 (1 * 0 * -4 = 0)

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 15
-4 <= grid[i][j] <= 4

lightbulb

解题思路

方法一：动态规划

我们定义一个三维数组 $f$ ，其中 $f[i][j][0]$ 和 $f[i][j][1]$ 分别表示从左上角 $(0, 0)$ 出发到达位置 $(i, j)$ 的路径中积的最小值和最大值。对于每个位置 $(i, j)$ ，我们可以从上方 $(i - 1, j)$ 或左方 $(i, j - 1)$ 转移过来，因此我们需要考虑这两条路径的积的最小值和最大值与当前单元格的值相乘后的结果。

最后，我们需要返回 $f[m - 1][n - 1][1]$ 对 $10^9 + 7$ 取余的结果，如果 $f[m - 1][n - 1][1]$ 小于 $0$ ，则返回 $-1$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[[0, 0] for _ in range(n)] for _ in range(m)]

        for i in range(m):
            for j in range(n):
                x = grid[i][j]
                if i == 0 and j == 0:
                    f[i][j][0] = x
                    f[i][j][1] = x
                    continue

                mn, mx = inf, -inf

                if i > 0:
                    a, b = f[i - 1][j]
                    mn = min(mn, a * x, b * x)
                    mx = max(mx, a * x, b * x)

                if j > 0:
                    a, b = f[i][j - 1]
                    mn = min(mn, a * x, b * x)
                    mx = max(mx, a * x, b * x)

                f[i][j][0], f[i][j][1] = mn, mx

        ans = f[m - 1][n - 1][1]
        mod = 10**9 + 7
        return -1 if ans < 0 else ans % mod

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate's understanding of state transition dynamic programming should be evident in how they handle both maximum and minimum products.
question_mark
They should be able to explain why maintaining both max and min products is crucial in the context of negative numbers.
question_mark
Look for clarity in explaining how modulo operations are applied and how it affects large results.

warning

常见陷阱

外企场景

error
Failing to account for negative numbers and their effect on the product, which may lead to incorrect results.
error
Not handling the modulo operation correctly, leading to overflow or incorrect final results.
error
Incorrectly assuming that all paths will have non-negative products, leading to incorrect edge case handling.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider using this approach for similar grid-based dynamic programming problems with path constraints.
arrow_right_alt
Variant could involve adding diagonal movement, requiring an additional transition step.
arrow_right_alt
Extend this to 3D grids, where moves can be made in three dimensions instead of two.

help

常见问题

外企场景

继续练习

#1595 连通两组点的最小成本 #1504 统计全 1 子矩形 #1463 摘樱桃 II