Maximum Difference Score in a Grid
Source: leetcode
Difficulty: Medium
Tags: array, dynamic-programming, matrix

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.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:**


![](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 <= 105`
- `1 <= grid[i][j] <= 105`




C++ solution:
class Solution {
public:
    int maxScore(vector<vector<int>>& a) 
    {
        int n=a.size(),m=a[0].size(),ans=INT_MIN;
        vector<vector<int>>dp(n,vector<int>(m));
        dp[n-1][m-1]=a[n-1][m-1];
        for(int i=n-2;i>=0;i--)
        {
            ans=max(ans,dp[i+1][m-1]-a[i][m-1]);
            dp[i][m-1]=max(a[i][m-1],dp[i+1][m-1]);
        }
        for(int i=m-2;i>=0;i--)
        {
            ans=max(ans,dp[n-1][i+1]-a[n-1][i]);
           dp[n-1][i]=max(a[n-1][i],dp[n-1][i+1]);
        }
        for(int i=n-2;i>=0;i--)
        {
            for(int j=m-2;j>=0;j--)
            {
                int val=max(dp[i+1][j],dp[i][j+1]);
                ans=max(ans,val-a[i][j]);
                dp[i][j]=max(val,a[i][j]);
            }
        }
        return ans;
    }
};
auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();

Go solution:
func maxScore(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	dp := make([][]int, m)
	res := math.MinInt
	for i := range m {
		dp[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			val := math.MaxInt
			if In(grid, i-1, j) {
				val = min(val, dp[i-1][j])
			}
			if In(grid, i, j-1) {
				val = min(val, dp[i][j-1])
			}
			res = max(res, grid[i][j]-val)
			dp[i][j] = min(val, grid[i][j])
		}
	}
	return res
}

func In[T any](mat [][]T, i, j int) bool {
	return i >= 0 && i < len(mat) &&
		j >= 0 && (len(mat) == 0 || j < len(mat[0]))
}

Java solution:
class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int m = grid.size(), n = grid.get(0).size();
        int ans[][] = new int[m][n];
        ans[m-1][n-1] = grid.get(m-1).get(n-1);
        for(int i=n-2;i>=0;i--)
        {
            ans[m-1][i]=Math.max(ans[m-1][i+1],grid.get(m-1).get(i));
        }
        for(int i=m-2;i>=0;i--)
        {
            ans[i][n-1]=Math.max(ans[i+1][n-1], grid.get(i).get(n-1));
        }
        for(int i=m-2;i>=0;i--)
        {
            for (int j=n-2;j>=0;j--)
            {
                ans[i][j] = Math.max(grid.get(i).get(j), Math.max(ans[i+1][j], ans[i][j+1]));
            }
        }
        int count = Integer.MIN_VALUE;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i+1<m)
                {
                    count=Math.max(count, ans[i+1][j]-grid.get(i).get(j));
                }
                if(j+1<n)
                {
                    count=Math.max(count, ans[i][j+1]-grid.get(i).get(j));
                }
                
            }
        }
        return count;
    }
}

JavaScript solution:
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxScore = function (grid) {
    const m = grid.length, n = grid[0].length;
    const dp = Array.from({ length: m }, () => []);
    let max = -Infinity;
    getMaxScore(0, 0);
    return max;

    function getMaxScore(row, col) {
        if (row >= m || col >= n) {
            return -Infinity;
        }

        if (dp[row][col] !== undefined) {
            return dp[row][col];
        }

        const bottom = getMaxScore(row + 1, col);
        const right = getMaxScore(row, col + 1);
        const currentMax = Math.max(bottom, right);
        max = Math.max(max, currentMax - grid[row][col]); // update max
        return dp[row][col] = Math.max(grid[row][col], currentMax);
    }
};

Python solution:
class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:

        bestPrv = [inf for _ in range(len(grid[0]))]
        ans = -inf
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if c>0 and bestPrv[c-1] < bestPrv[c]:
                    bestPrv[c] =  bestPrv[c-1]
                            
                if grid[r][c] - bestPrv[c] > ans:
                    ans = grid[r][c] - bestPrv[c]
                if grid[r][c] < bestPrv[c]:
                    bestPrv[c] = grid[r][c]
               
              

        return ans

Ruby solution:
def max_score(grid)
    m = grid.size
    n = grid[0].size
    best_prev = Array.new(n, Float::INFINITY)
    ans = -Float::INFINITY

    grid.each do |row|
        (0...n).each do |c|
            if c > 0 && best_prev[c-1] < best_prev[c]
                best_prev[c] = best_prev[c-1]
            end
            current_score = row[c] - best_prev[c]
            ans = current_score if current_score > ans
            if row[c] < best_prev[c]
                best_prev[c] = row[c]
            end
        end
    end

    ans
end