DP 10ms - Java O(M*N) | O(M*N)
Intuition\n Describe your first thoughts on how to solve this problem. \nDP 2D matrix to track max score of every cell can get from top and left. Along the way,
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDP 2D matrix to track max score of every cell can get from top and left. Along the way, collect the global max and min for return.\n```\ndp[i][j] = max(0, dp[i - 1][j] + (mat[i][j] - mat[i - 1][j]), dp[i][j - 1] + (mat[i][j] - mat[i][j - 1]))\n```\n\nNote: in the case that global max is `0`, it still requires to make at leat one move. But there is no higher value cell to move to since the global max is `0`, this means we have to move to the cell with closest equal or lower value. This is why we tracks the global min too.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int maxScore(List<List<Integer>> grid) {\n        // DP: 2d - dp[i][j] = max(dp[i-1][j],dp[i][j-1],0)\n        // also if the dp[i][j] is 0, update the min in case the max is 0\n        int n = grid.size() + 1, m = grid.get(0).size() + 1;\n        int[][] mat = new int[n][m], dp = new int[n][m];\n        int x = 1, y = 1;\n        for (List<Integer> row : grid) {\n            for (int cell : row) {\n                mat[x][y++] = cell;\n            }\n            x++;\n            y = 1;\n        }\n        for (int i = 0; i < n; i++)\n            mat[i][0] = Integer.MAX_VALUE;\n        for (int j = 0; j < m; j++)\n            mat[0][j] = Integer.MAX_VALUE;\n        int min = Integer.MIN_VALUE, max = 0, max_i = 0, max_j = 0;\n        for (int i = 1; i < n; i++)\n            for (int j = 1; j < m; j++) {\n                int valUp = dp[i - 1][j] + (mat[i][j] - mat[i - 1][j]);\n                int valLeft = dp[i][j - 1] + (mat[i][j] - mat[i][j - 1]);\n                dp[i][j] = Math.max(0, Math.max(valUp, valLeft));\n                max = Math.max(max, dp[i][j]);\n                if (valUp <= 0)\n                    min = Math.max(min, valUp);\n                if (valLeft <= 0)\n                    min = Math.max(min, valLeft);\n                // System.out.printf("up:%d, left:%d, dp:%d\\n", valUp, valLeft, dp[i][j]);\n            }\n        return max != 0 ? max : min;\n    }\n}\n```
['Java']