Intuitive DP solution
Intuition\nBy looking at the equation for finding the max difference, we can see that the result is equal to the max destination - origin.\n\nfor example, for t
# Intuition\nBy looking at the equation for finding the max difference, we can see that the result is equal to the max destination - origin.\n\nfor example, for the path c1 -> c4, (c2 - c1) + (c3 - c2) + (c4 - c3) = c4 - c1. The intermediary steps cancel out.\n\nThen, the problem becomes finding the maximum difference from each origin. We know to optimize for this difference we have to subtract a cell value from the previously found minimum above or to the left of the current value.\n\nWe loop through every spot in the grid, \n\nFirst we find the current minimum, which is the minimum of the left cell and above cell. Then the maximum of the current cell and the current minimum and the curren result is set to the result. Then we update the dp array with the new minimum.\n\nComplexity is easy O(mn) for both, but we could save space by using the grid provided for tracking the minimum.\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\n        dp = [[10e5 for _ in range(n)] for _ in range(m)]\n\n        # dp[i][j] = current minimum\n\n\n        res = -10e5\n        for i in range(m):\n            for j in range(n):\n                curr = min(dp[i - 1][j] if i > 0 else 10e5, dp[i][j - 1] if j > 0 else 10e5)\n                res = max(res, grid[i][j] - curr)\n                dp[i][j] = min(grid[i][j], curr)\n        return res\n                \n\n        \n```
['Python3']