Maximum difference score in a grid

Array Dynamic Programming Matrix

47.7% acceptance

Feb 24, 2026

287

You are given an m x n matrix grid consisting of positive integers. You can move from a cell in the matrix to any other cell that is either to the bottom or to the right (not necessarily adjacent). The score of a move from a cell with value c1 to a cell with value c2 is c2 - c1. You can start at any cell, and you have to make at least one move. Return the maximum total score you can achieve.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    // Score of any path = last_value - first_value (telescoping)
    // Maximize grid[r2][c2] - min(grid[r1][c1]) for all (r1,c1) that can reach (r2,c2)
    // min_dp[r][c] = min grid value in the rectangle [0..r][0..c] (i.e., all cells reachable from)
    let mut min_dp = vec![vec![i32::MAX; n]; m];
    let mut ans = i32::MIN;
    for r in 0..m {
      for c in 0..n {
        let mut min_prev = i32::MAX;
        if r > 0 {
          min_prev = min_prev.min(min_dp[r - 1][c]);
        }
        if c > 0 {
          min_prev = min_prev.min(min_dp[r][c - 1]);
        }
        if min_prev != i32::MAX {
          ans = ans.max(grid[r][c] - min_prev);
        }
        min_dp[r][c] = grid[r][c].min(if min_prev == i32::MAX { grid[r][c] } else { min_prev });
      }
    }
    ans
  }
}