Maximum non negative product in a matrix

Array Dynamic Programming Matrix

35.7% acceptance

Feb 25, 2026

939

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 10^9 + 7. If the maximum product is negative, return -1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_product_path(grid: Vec<Vec<i32>>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let m = grid.len();
    let n = grid[0].len();
    // dp_max[r][c] = max product to reach (r,c)
    // dp_min[r][c] = min product to reach (r,c) (for tracking negatives)
    let mut dp_max = vec![vec![0i64; n]; m];
    let mut dp_min = vec![vec![0i64; n]; m];
    dp_max[0][0] = grid[0][0] as i64;
    dp_min[0][0] = grid[0][0] as i64;

    for c in 1..n {
      dp_max[0][c] = dp_max[0][c - 1] * grid[0][c] as i64;
      dp_min[0][c] = dp_min[0][c - 1] * grid[0][c] as i64;
    }
    for r in 1..m {
      dp_max[r][0] = dp_max[r - 1][0] * grid[r][0] as i64;
      dp_min[r][0] = dp_min[r - 1][0] * grid[r][0] as i64;
    }

    for r in 1..m {
      for c in 1..n {
        let g = grid[r][c] as i64;
        let candidates = [
          dp_max[r - 1][c] * g,
          dp_min[r - 1][c] * g,
          dp_max[r][c - 1] * g,
          dp_min[r][c - 1] * g,
        ];
        dp_max[r][c] = *candidates.iter().max().unwrap();
        dp_min[r][c] = *candidates.iter().min().unwrap();
      }
    }

    let ans = dp_max[m - 1][n - 1];
    if ans < 0 {
      -1
    } else {
      (ans % MOD) as i32
    }
  }
}