Easiest Python Solution 100% Beat - O(m*n) Time and O(1) Extra Space
Intuition\nThe first thing to notice is that the maximum score can always come from a single move. Consider the case we have a maximum score with multiple moves
# Intuition\nThe first thing to notice is that the maximum score can always come from a single move. Consider the case we have a maximum score with multiple moves. Let\'s assume that it start\'s with a value $$v_1$$ and ends with a value $$v_n$$. We know that the score of the path is $$v_1 - v_n$$ and as a part of going from start to end, we have to go through $$v_1 \\to v_2 \\to \\ldots \\to v_{n-1} \\to v_n$$. We know that by the conditions in the problem, all $$v_i$$ must be the the bottom and right $$v_1$$. Therefore, we have a path with an equivalent score that is $$v_1 \\to v_n$$. \n\n# Approach\nGiven the inuition described above, for each cell in the matrix, if we can store what the minimum value is to the top and left of any cell, we can calculate the maximum score using the current cell value and the minimum value. We can do this using a DP approach where we check the cell directly upwards and leftwards of any cell. Since we can reuse the original grid array, we use no extra space. \n\n# Complexity\n- Time complexity: $$O(n \\times m)$$\n\n- Space complexity: $$O(1)$$\n\n# Code\n```\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        m = len(grid)\n        n = len(grid[0])\n        ans = float(\'-inf\')\n\n        for i in range(m):\n            for k in range(n):\n                min_at_pos = min(grid[i-1][k] if i!=0 else float(\'inf\'), grid[i][k-1] if k!=0 else float(\'inf\'))\n                t = grid[i][k]\n                ans = max(ans,  grid[i][k]-min_at_pos)\n                grid[i][k] = min(min_at_pos, t)\n\n        return ans\n```
['Dynamic Programming', 'Matrix', 'Python', 'Python3']