# Maximum Difference Score in a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-difference-score-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/maximum-difference-score-in-a-grid
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit)
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-difference-score-in-a-grid/image0.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:**

![](https://assets.glich.co/dsa/maximum-difference-score-in-a-grid/image1.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 <= 105`
* `1 <= grid[i][j] <= 105`

# Approaches
## Brute Force Enumeration
The problem asks for the maximum score from a sequence of moves. A key observation is that the total score of a path from a starting cell `(r0, c0)` to an ending cell `(rk, ck)` is a telescoping sum that simplifies to `grid[rk][ck] - grid[r0][c0]`. Therefore, the problem reduces to finding the maximum difference `grid[r2][c2] - grid[r1][c1]` such that a path can exist from `(r1, c1)` to `(r2, c2)`. A path exists if `r2 >= r1`, `c2 >= c1`, and `(r1, c1) != (r2, c2)`.

A brute-force approach directly implements this simplified problem. It involves checking every possible pair of start and end cells in the grid that satisfy the movement constraints, calculating their difference, and keeping track of the maximum difference found.
**Time:** O(m² * n²), where `m` is the number of rows and `n` is the number of columns. This is due to four nested loops iterating over the grid dimensions. · **Space:** O(1) extra space.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small grids.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
This method iterates through every possible start cell `(r1, c1)` and every possible end cell `(r2, c2)`. For each pair, it first validates if a move from `(r1, c1)` to `(r2, c2)` is legitimate. According to the problem, we can move to any cell to the bottom or right, which means `r2 >= r1` and `c2 >= c1`. We also need to make at least one move, so the start and end cells cannot be the same. If these conditions are met, we calculate the score and update our maximum score if the current score is higher.

```java
import java.util.List;

class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int m = grid.size();
        int n = grid.get(0).size();
        int maxScore = Integer.MIN_VALUE;

        for (int r1 = 0; r1 < m; r1++) {
            for (int c1 = 0; c1 < n; c1++) {
                for (int r2 = r1; r2 < m; r2++) {
                    for (int c2 = c1; c2 < n; c2++) {
                        if (r1 == r2 && c1 == c2) {
                            continue;
                        }
                        int score = grid.get(r2).get(c2) - grid.get(r1).get(c1);
                        if (score > maxScore) {
                            maxScore = score;
                        }
                    }
                }
            }
        }
        return maxScore;
    }
}
```
### Algorithm
*   Initialize `max_score` to a very small number (e.g., `Integer.MIN_VALUE`).
*   Use four nested loops to iterate through all possible pairs of start cells `(r1, c1)` and end cells `(r2, c2)`.
*   The outer two loops iterate through `r1` from `0` to `m-1` and `c1` from `0` to `n-1`.
*   The inner two loops iterate through `r2` from `r1` to `m-1` and `c2` from `c1` to `n-1`.
*   Inside the innermost loop, check if the start and end cells are the same (`r1 == r2` and `c1 == c2`). If they are, skip this pair as at least one move is required.
*   If the cells are different, calculate the score: `score = grid[r2][c2] - grid[r1][c1]`.
*   Update `max_score = max(max_score, score)`.
*   After all pairs have been checked, return `max_score`.

## Dynamic Programming with 2D DP Table
The brute-force approach is inefficient because it repeatedly calculates the minimum value in the top-left subgrid for each potential end cell. We can optimize this using dynamic programming. The idea is to build a DP table that, for each cell `(i, j)`, stores the minimum value encountered in the rectangular subgrid from `(0, 0)` to `(i, j)`. By traversing the grid once, we can both populate this DP table and calculate the maximum score simultaneously.
**Time:** O(m * n) as we iterate through each cell of the grid exactly once. · **Space:** O(m * n) to store the 2D DP table.
**Pros:** Efficient time complexity, suitable for the given constraints.; Conceptually a clear improvement over brute force by avoiding redundant computations.
**Cons:** Requires extra space proportional to the size of the grid, which might be large.
### Explanation
We define `dp[i][j]` as the minimum value in the grid within the rectangle defined by corners `(0, 0)` and `(i, j)`. The recurrence relation for this is `dp[i][j] = min(grid[i][j], dp[i-1][j], dp[i][j-1])` for `i, j > 0`, with base cases for the first row and column.

As we iterate through the grid to compute `dp[i][j]`, we can also find the maximum score. For any cell `(i, j)`, any preceding cell `(r, c)` (where `r <= i, c <= j, (r,c) != (i,j)`) is a potential start cell. The minimum value among all such preceding cells is `min_prev = min(dp[i-1][j], dp[i][j-1])`. The maximum score ending at `(i, j)` is thus `grid[i][j] - min_prev`. We update our global `max_score` with this value if it's greater.

```java
import java.util.List;

class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int m = grid.size();
        int n = grid.get(0).size();
        int[][] dp = new int[m][n];
        int maxScore = Integer.MIN_VALUE;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int minPrev = Integer.MAX_VALUE;
                if (i > 0) {
                    minPrev = Math.min(minPrev, dp[i - 1][j]);
                }
                if (j > 0) {
                    minPrev = Math.min(minPrev, dp[i][j - 1]);
                }

                if (minPrev != Integer.MAX_VALUE) {
                    maxScore = Math.max(maxScore, grid.get(i).get(j) - minPrev);
                }

                dp[i][j] = grid.get(i).get(j);
                if (minPrev != Integer.MAX_VALUE) {
                    dp[i][j] = Math.min(dp[i][j], minPrev);
                }
            }
        }
        return maxScore;
    }
}
```
### Algorithm
*   Create a 2D DP array, `dp`, of the same dimensions as the grid, `m x n`.
*   `dp[i][j]` will store the minimum value found in the grid in the rectangle from `(0, 0)` to `(i, j)`.
*   Initialize `max_score` to `Integer.MIN_VALUE`.
*   Iterate through the grid with indices `i` from `0` to `m-1` and `j` from `0` to `n-1`.
*   For each cell `(i, j)`:
    *   Calculate `min_prev`, the minimum value in the grid in the region that can precede `(i, j)`. This is `min(dp[i-1][j], dp[i][j-1])` (handling edge cases for the first row and column).
    *   If `min_prev` is valid (i.e., not at the very first cell `(0,0)`), calculate a potential score: `score = grid[i][j] - min_prev`. Update `max_score = max(max_score, score)`.
    *   Update the DP table for the current cell: `dp[i][j] = min(grid[i][j], min_prev)`.
*   Return `max_score`.

## Space-Optimized Dynamic Programming
The 2D DP approach can be further optimized in terms of space. When computing the DP values for the current row `i`, we only need information from the previous row `i-1` and the elements already computed in the current row. This observation allows us to reduce the space complexity from `O(m * n)` to `O(n)` (or `O(min(m, n))` by choosing to iterate over the smaller dimension) by using a single 1D array to store the necessary DP state.
**Time:** O(m * n), as we still need to visit every cell in the grid once. · **Space:** O(n), where `n` is the number of columns. If we iterate column-wise when `m < n`, the space can be O(min(m, n)).
**Pros:** Optimal time complexity.; Optimal space complexity, making it very efficient for large grids.
**Cons:** The logic for in-place updates in the 1D DP array can be slightly harder to reason about compared to the 2D version.
### Explanation
We use a single 1D array, `dp`, of size `n`. As we iterate through row `i`, `dp[j]` will be updated to store the minimum prefix value up to cell `(i, j)`. When we are at cell `(i, j)`, the value currently in `dp[j]` is the minimum prefix value from the row above, i.e., `min_prefix[i-1][j]`. The value `dp[j-1]` has already been updated for the current row `i`, so it holds `min_prefix[i][j-1]`. Thus, the minimum value from all preceding cells is `min_prev = min(dp[j], dp[j-1])`. We use this `min_prev` to calculate a potential score and then update `dp[j]` to `min(grid[i][j], min_prev)` for the current cell, which will then be used for calculations in the next row.

```java
import java.util.List;
import java.util.Arrays;

class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int m = grid.size();
        int n = grid.get(0).size();
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        int maxScore = Integer.MIN_VALUE;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int minPrev = Integer.MAX_VALUE;
                // min from cell above is dp[j] (from previous row i-1)
                if (i > 0) {
                    minPrev = Math.min(minPrev, dp[j]);
                }
                // min from cell to the left is dp[j-1] (from current row i)
                if (j > 0) {
                    minPrev = Math.min(minPrev, dp[j - 1]);
                }

                if (minPrev != Integer.MAX_VALUE) {
                    maxScore = Math.max(maxScore, grid.get(i).get(j) - minPrev);
                }

                // Update dp[j] for the current row i
                int minIncludingCurrent = grid.get(i).get(j);
                if (minPrev != Integer.MAX_VALUE) {
                    minIncludingCurrent = Math.min(minIncludingCurrent, minPrev);
                }
                dp[j] = minIncludingCurrent;
            }
        }
        return maxScore;
    }
}
```
### Algorithm
*   Create a 1D DP array, `dp`, of size `n`.
*   Initialize `max_score` to `Integer.MIN_VALUE`.
*   Iterate through the grid with outer loop for rows `i` from `0` to `m-1` and inner loop for columns `j` from `0` to `n-1`.
*   For each cell `(i, j)`:
    *   Calculate `min_prev`. The minimum from the cell above `(i-1, j)` is stored in `dp[j]` (from the previous row's computation). The minimum from the cell to the left `(i, j-1)` is stored in `dp[j-1]` (which was just updated in the current row's computation).
    *   `min_prev = min(dp[j] (if i>0), dp[j-1] (if j>0))`.
    *   If `min_prev` is valid, calculate `score = grid[i][j] - min_prev` and update `max_score`.
    *   Update `dp[j]` for the current row `i`: `dp[j] = min(grid[i][j], min_prev)`. This new value in `dp[j]` now represents the minimum prefix value up to `(i, j)`.
*   Return `max_score`.

# Solutions
### Java

```java
class Solution {
public
  int maxScore(List<List<Integer>> grid) {
    int m = grid.size(), n = grid.get(0).size();
    final int inf = 1 << 30;
    int ans = -inf;
    int[][] f = new int[m][n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int mi = inf;
        if (i > 0) {
          mi = Math.min(mi, f[i - 1][j]);
        }
        if (j > 0) {
          mi = Math.min(mi, f[i][j - 1]);
        }
        ans = Math.max(ans, grid.get(i).get(j) - mi);
        f[i][j] = Math.min(grid.get(i).get(j), mi);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxScore(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    const int inf = 1 << 30;
    int ans = -inf;
    int f[m][n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int mi = inf;
        if (i) {
          mi = min(mi, f[i - 1][j]);
        }
        if (j) {
          mi = min(mi, f[i][j - 1]);
        }
        ans = max(ans, grid[i][j] - mi);
        f[i][j] = min(grid[i][j], mi);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxScore(self, grid: List[List[int]]) -> int: f = [[0] * len(grid[0]) for _ in range(len(grid))] ans = - inf for i, row in enumerate(grid): for j, x in enumerate(row): mi = inf if i: mi = min(mi, f[i - 1][j]) if j: mi = min(mi, f[i][j - 1]) ans = max(ans, x - mi) f[i][j] = min(x, mi) return ans

```