[C++] with Picture Explanation, DP
Intuition\nThe short simple answer to this problem is that the answer is almost equal to the max value in the matrix minus the minimum value in the matrix.\nHow
# Intuition\nThe short simple answer to this problem is that the answer is almost equal to the max value in the matrix minus the minimum value in the matrix.\nHowever, obviously there is more to this.\nLet\'s show why the above is true to a good extent.\nImagine the value in grid[i+k][j+t] (such that t,k>0) is larger than grid[i][j]. Then it will be easy to see **the path is irrelevant**. Thus, since there is always a path between the smallest value and the larger value, we should be good to calulate this value.\n![ohjbkjs.jpg](https://assets.leetcode.com/users/images/54268a05-cce5-4269-9efc-69a89f3f7661_1715487336.885872.jpeg)\nNote that, not always the largest value will be in the bottom right and the smallest value in the upper left matrices. Thus, we need to do a **Dynamic Programming** with memorization approach. Some folks do it inplace, I rather do it in a different matrix. Depends on your preference (and space requirement).\n![bbddp.jpg](https://assets.leetcode.com/users/images/4821c400-0611-4a36-83ef-0f0e371c8109_1715494671.3016415.jpeg)\n\n\n\n\n# Approach\n**Case 1 (Non-Descending matrix):** So we can reach to grid[i+k][j]  with `grid[i+k][j]-grid[i][j]`; and then to grid[i+k][j+t] with `grid[i+k][j+t]-grid[i+k][j]` \nso the entire move will be equal to = `grid[i+k][j+t]-grid[i][j]` \nThus, we see that for each grid[i+k][j+t] that we end the path, we just need to know **where the starting point was** (which will be  the *smallest* value in the *upper left* matrix of a grid point).\n\n**Case 2 (Descending matrix):** Because the problem states that there needs to be *at least one move*, there is this exception that we need to keep track of whether all the values are in descending order or not. In this case, memorize the difference of the smallest value seen in the **upper left matrix** and the grid[i][j] value. At the end, check for descending case, and if so, output the seen minimum diff.\n\n# Complexity\n- Time complexity: \nO(m*n)\n\n- Space complexity:\nO(m*n)\n\n# Code\n```\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        vector<vector<int>> smallest ((int)grid.size(),vector<int>((int)grid[0].size(),0)); // DP matrix to determine the smallest value \n                                        // between coordinates [0][0] and [i][j]\n        smallest[0][0] = grid[0][0];\n        int minDiffIfAllDesc = INT_MIN; // We return the diff if the matrix is all descending\n        bool allDescending = true; // Initially assume the matrix is all descending\n        \n        // fill the first column of smallest\n        for(int i = 1;i<grid.size();i++){\n            if (allDescending && smallest[i-1][0]<=grid[i][0]){\n                allDescending = false;\n            }else{\n                minDiffIfAllDesc = max(minDiffIfAllDesc, grid[i][0] - smallest[i-1][0]); // update for allDescending\n            }\n            smallest[i][0] = min(smallest[i-1][0],grid[i][0]);\n        }\n\n        // fill the first row of smallest\n        for(int j = 1;j<grid[0].size();j++){ \n            if (allDescending && smallest[0][j-1]<=grid[0][j]){\n                allDescending = false;\n            }else{\n                 minDiffIfAllDesc = max(minDiffIfAllDesc, grid[0][j] - smallest[0][j-1]); // update\n            }\n            smallest[0][j] = min(smallest[0][j-1],grid[0][j]);\n        }\n\n        // fill the rest of the smallest dp matrix\n        for(int i = 1;i<grid.size();i++){\n            for(int j = 1;j<grid[0].size();j++){\n                smallest[i][j] = min(smallest[i-1][j],smallest[i][j-1]);\n                if (allDescending && smallest[i][j]<=grid[i][j]){\n                    allDescending = false;\n                }else{\n                    minDiffIfAllDesc = max(minDiffIfAllDesc, grid[i][j] - smallest[i][j]); // update\n                }\n                smallest[i][j] = min(smallest[i][j],grid[i][j]);\n            }    \n        }\n\n        if (allDescending){\n            return minDiffIfAllDesc; // this is when matrix is all descending\n        }\n\n        // We return the mmax value if the matrix is NOT all descending\n        int mmax = INT_MIN; \n        for(int i = 0;i<grid.size();i++){\n            for(int j = 0;j<grid[0].size();j++){\n                mmax = max(mmax,grid[i][j]-smallest[i][j]);    \n            }    \n        }\n        return mmax;\n    }\n};\n```
['C++']