Problem

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 the value c1 to a cell with the 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


![](https://assets.leetcode.com/uploads/2024/03/14/grid1.png)

Input: grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]

Output: 9

Explanation: We start at the cell `(0, 1)`, and we perform the following
moves:  
\- Move from the cell `(0, 1)` to `(2, 1)` with a score of `7 - 5 = 2`.  
\- Move from the cell `(2, 1)` to `(2, 2)` with a score of `14 - 7 = 7`.  
The total score is `2 + 7 = 9`.

Example 2

1
2
3
4
5
6
7
8
9


![](https://assets.leetcode.com/uploads/2024/04/08/moregridsdrawio-1.png)

Input: grid = [[4,3,2],[3,2,1]]

Output: -1

Explanation: We start at the cell `(0, 0)`, and we perform one move: `(0,
0)` to `(0, 1)`. The score is `3 - 4 = -1`.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 10^5

Solution

Method 1 – Dynamic Programming with Suffix Minimum

Intuition

To maximize the score, for each cell, we want to find the minimum value in the submatrix to its bottom-right (including itself), and then for each cell, check the difference between any cell to its right or below and itself. We can precompute the minimum value for each bottom-right submatrix using DP.

Approach

  1. Create a min_suf matrix where min_suf[i][j] is the minimum value in the submatrix starting at (i, j) to the bottom-right corner.
  2. Fill min_suf from bottom-right to top-left.
  3. For each cell (i, j), check all possible moves to the right or below (i.e., any cell (x, y) with x >= i and y >= j), but we only need to check the minimum in the submatrix.
  4. The maximum score is the maximum of min_suf[x][y] - grid[i][j] for all valid moves.
  5. Return the maximum score.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int maxScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> min_suf(m, vector<int>(n));
        for (int i = m-1; i >= 0; --i) {
            for (int j = n-1; j >= 0; --j) {
                min_suf[i][j] = grid[i][j];
                if (i+1 < m) min_suf[i][j] = min(min_suf[i][j], min_suf[i+1][j]);
                if (j+1 < n) min_suf[i][j] = min(min_suf[i][j], min_suf[i][j+1]);
                if (i+1 < m && j+1 < n) min_suf[i][j] = min(min_suf[i][j], min_suf[i+1][j+1]);
            }
        }
        int ans = INT_MIN;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i+1 < m) ans = max(ans, min_suf[i+1][j] - grid[i][j]);
                if (j+1 < n) ans = max(ans, min_suf[i][j+1] - grid[i][j]);
            }
        }
        return ans;
    }
};
 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
32
33

func maxScore(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    minSuf := make([][]int, m)
    for i := range minSuf {
        minSuf[i] = make([]int, n)
    }
    for i := m-1; i >= 0; i-- {
        for j := n-1; j >= 0; j-- {
            minSuf[i][j] = grid[i][j]
            if i+1 < m && minSuf[i+1][j] < minSuf[i][j] {
                minSuf[i][j] = minSuf[i+1][j]
            }
            if j+1 < n && minSuf[i][j+1] < minSuf[i][j] {
                minSuf[i][j] = minSuf[i][j+1]
            }
            if i+1 < m && j+1 < n && minSuf[i+1][j+1] < minSuf[i][j] {
                minSuf[i][j] = minSuf[i+1][j+1]
            }
        }
    }
    ans := math.MinInt32
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i+1 < m && minSuf[i+1][j]-grid[i][j] > ans {
                ans = minSuf[i+1][j] - grid[i][j]
            }
            if j+1 < n && minSuf[i][j+1]-grid[i][j] > ans {
                ans = minSuf[i][j+1] - grid[i][j]
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int maxScore(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] minSuf = new int[m][n];
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                minSuf[i][j] = grid[i][j];
                if (i+1 < m) minSuf[i][j] = Math.min(minSuf[i][j], minSuf[i+1][j]);
                if (j+1 < n) minSuf[i][j] = Math.min(minSuf[i][j], minSuf[i][j+1]);
                if (i+1 < m && j+1 < n) minSuf[i][j] = Math.min(minSuf[i][j], minSuf[i+1][j+1]);
            }
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i+1 < m) ans = Math.max(ans, minSuf[i+1][j] - grid[i][j]);
                if (j+1 < n) ans = Math.max(ans, minSuf[i][j+1] - grid[i][j]);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun maxScore(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val minSuf = Array(m) { IntArray(n) }
        for (i in m-1 downTo 0) {
            for (j in n-1 downTo 0) {
                minSuf[i][j] = grid[i][j]
                if (i+1 < m) minSuf[i][j] = minOf(minSuf[i][j], minSuf[i+1][j])
                if (j+1 < n) minSuf[i][j] = minOf(minSuf[i][j], minSuf[i][j+1])
                if (i+1 < m && j+1 < n) minSuf[i][j] = minOf(minSuf[i][j], minSuf[i+1][j+1])
            }
        }
        var ans = Int.MIN_VALUE
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (i+1 < m) ans = maxOf(ans, minSuf[i+1][j] - grid[i][j])
                if (j+1 < n) ans = maxOf(ans, minSuf[i][j+1] - grid[i][j])
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def maxScore(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        min_suf = [[0]*n for _ in range(m)]
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                min_suf[i][j] = grid[i][j]
                if i+1 < m:
                    min_suf[i][j] = min(min_suf[i][j], min_suf[i+1][j])
                if j+1 < n:
                    min_suf[i][j] = min(min_suf[i][j], min_suf[i][j+1])
                if i+1 < m and j+1 < n:
                    min_suf[i][j] = min(min_suf[i][j], min_suf[i+1][j+1])
        ans = float('-inf')
        for i in range(m):
            for j in range(n):
                if i+1 < m:
                    ans = max(ans, min_suf[i+1][j] - grid[i][j])
                if j+1 < n:
                    ans = max(ans, min_suf[i][j+1] - grid[i][j])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn max_score(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut min_suf = vec![vec![0; n]; m];
        for i in (0..m).rev() {
            for j in (0..n).rev() {
                min_suf[i][j] = grid[i][j];
                if i+1 < m { min_suf[i][j] = min_suf[i][j].min(min_suf[i+1][j]); }
                if j+1 < n { min_suf[i][j] = min_suf[i][j].min(min_suf[i][j+1]); }
                if i+1 < m && j+1 < n { min_suf[i][j] = min_suf[i][j].min(min_suf[i+1][j+1]); }
            }
        }
        let mut ans = i32::MIN;
        for i in 0..m {
            for j in 0..n {
                if i+1 < m { ans = ans.max(min_suf[i+1][j] - grid[i][j]); }
                if j+1 < n { ans = ans.max(min_suf[i][j+1] - grid[i][j]); }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    maxScore(grid: number[][]): number {
        const m = grid.length, n = grid[0].length;
        const minSuf = Array.from({length: m}, () => Array(n).fill(0));
        for (let i = m-1; i >= 0; i--) {
            for (let j = n-1; j >= 0; j--) {
                minSuf[i][j] = grid[i][j];
                if (i+1 < m) minSuf[i][j] = Math.min(minSuf[i][j], minSuf[i+1][j]);
                if (j+1 < n) minSuf[i][j] = Math.min(minSuf[i][j], minSuf[i][j+1]);
                if (i+1 < m && j+1 < n) minSuf[i][j] = Math.min(minSuf[i][j], minSuf[i+1][j+1]);
            }
        }
        let ans = -Infinity;
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (i+1 < m) ans = Math.max(ans, minSuf[i+1][j] - grid[i][j]);
                if (j+1 < n) ans = Math.max(ans, minSuf[i][j+1] - grid[i][j]);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(mn), where m and n are the grid dimensions, since each cell is visited a constant number of times.
  • 🧺 Space complexity: O(mn), for the suffix minimum matrix.