O(N*M) Time Complexity, Simple DP Solution
The key idea is to find the minimum element in the top left region and then take the maximum among the difference of grid and the minimum array constructed.\n\n
The key idea is to find the minimum element in the top left region and then take the maximum among the difference of grid and the minimum array constructed.\n\nThis is because going from a->b->c gives the answer as (b-a)+(c-b) which is essentially (c-a).\n\n\n**Python:**\n\n```\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        n = len(grid)\n        m = len(grid[0])\n        arr =[[0]*(m) for _ in range(n)]\n        \n        for i in range(n):\n            \n            arr[i][0] = grid[i][0]\n            if i>0:\n                arr[i][0] = min(grid[i-1][0],arr[i-1][0])\n        \n        for j in range(m):\n            arr[0][j] = grid[0][j]\n            if j>0:\n                arr[0][j] = min(grid[0][j-1],arr[0][j-1])\n    \n        for i in range(1,n):\n            for j in range(1,m):\n                arr[i][j] = min(arr[i-1][j], arr[i][j-1], arr[i-1][j-1], grid[i-1][j-1], grid[i][j-1], grid[i-1][j])\n        print(arr)\n        ans = -1e9\n        for i in range(n):\n            for j in range(m):\n                if i==0 and j==0:\n                    continue\n                ans = max(ans, grid[i][j]-arr[i][j])\n        return ans\n\n\n```\n\n**C++:**\n\n```\n\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m=grid[0].size();\n        \n        vector<vector<int>> arr(n,vector<int>(m,0));\n        \n        for(int i=0;i<n;i++){\n            arr[i][0] = grid[i][0];\n            if (i>0){\n                arr[i][0] = min(arr[i-1][0],grid[i-1][0]);\n            }\n        }\n        \n        for(int j=0;j<m;j++){\n            arr[0][j] = grid[0][j];\n            if (j>0){\n                arr[0][j] = min(arr[0][j-1],grid[0][j-1]);\n            }\n        }\n        \n        for(int i=1;i<n;i++){\n            for(int j=1;j<m;j++){\n                arr[i][j] = min({arr[i-1][j],arr[i-1][j-1],arr[i][j-1],grid[i-1][j],grid[i-1][j-1],grid[i][j-1]});\n            }\n        }\n        int ans = INT_MIN;\n        \n        for(int i=0;i<n;i++){\n            for(int j=0;j<m;j++){\n                if(i==0 && j==0) continue;\n                ans = max(ans, grid[i][j] -arr[i][j]);\n            }\n        }\n        return ans;\n    }\n};\n\n\n```
['Dynamic Programming', 'Python']