Show problems as
Classic problem #1594MediumArrayDynamic ProgrammingMatrix

Maximum Non Negative Product in a Matrix

Real-world version: Strongest Signal Across the Amplifier Grid
Tracked in this browser only
Read Maximum Non Negative Product in a Matrix on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A test rig is a rectangular board of amplifier tiles, given as grid, where grid[r][c] is the gain of the tile in row r and column c. A gain may be negative, which means that tile inverts the signal.

A probe signal enters at the top-left tile with value 1 and must leave at the bottom-right tile. From a tile the probe may only step one tile to the right or one tile down. Every tile the probe occupies, including the entry tile and the exit tile, multiplies the running value by that tile's gain.

Among the routes whose final value is not negative, report the largest final value. Because that value can be enormous, report it modulo 1000000007. If every route ends on a negative value, return -1 instead.

Examples

Example 1

Input
grid = [[-2, 3], [4, -1]]
Output
8

Stepping down and then right puts the probe on -2, 4 and -1, so the value leaving the board is 8. That is not negative, and 8 reduced modulo 1000000007 is 8.

Example 2

Input
grid = [[2, -1, -1, 3, 1, 2]]
Output
12

The board is a single row, so the probe walks every tile: 2, -1, -1, 3, 1 and 2 multiply to 12.

Example 3

Input
grid = [[-1, 2], [3, 4]]
Output
-1

The two available routes leave the board holding -8 and -12. Neither is allowed, so the answer is -1.

Constraints

  • rows == grid.length
  • cols == grid[r].length
  • 1 <= rows, cols <= 15
  • -4 <= grid[r][c] <= 4
  • The reported value is the largest non-negative final value reduced modulo 1000000007, or -1.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_product_path(grid: list[list[int]]) -> int:
Java
public int maxProductPath(int[][] grid)

More on the same topics