Maximum Difference Score in a Grid
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
9 5 7 3 8 9 6 1 6 7 14 3 2 5 3 1
Input
grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]Output
9Starting at cell
(0, 1), moving to (2, 1) scores 7 - 5 = 2, then moving to (2, 2) scores 14 - 7 = 7, for a total score of 9.Example 2
4 3 2 3 2 1
Input
grid = [[4,3,2],[3,2,1]]Output
-1Starting at cell
(0, 0) and moving to (0, 1) gives a score of 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