Rectangle approach O(m*n)
Intuition\nThe largest jump with cell (a,b) is to find the smallest value of rectangle (0,0) -> (a,b) except the point at (a,b)\n Describe your first thoughts o
# Intuition\nThe largest jump with cell (a,b) is to find the smallest value of rectangle (0,0) -> (a,b) except the point at (a,b)\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n- Create an O(n) array that stores the smallest value before reaching cell (x,y) of row x.\n\n- When browsing to position (x,b), the smallest value for this cell will be = the smallest value of the left cell (x, b-1) and grid(x,b-1) compared to the smallest value of the cell above (x-1,b) and grid(x-1, b)\n\n- After finding the smallest value in the rectangle (0,0) -> (x,y), take the value of the cell grid(x,y) minus it, it will give the largest jump whose end point is cell (x,y) called step(x,y). At this time, we update the result res = min(res, step(x,y))\n\n- Finally return res\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(m*n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int maxScore(List<List<Integer>> grid) {\n        int res = Integer.MIN_VALUE;\n        int[] t = new int[grid.get(0).size()];\n        for (int i = 0; i < grid.size(); i++) {\n            for (int j = 0; j < grid.get(0).size(); j++) {\n                if (i == 0) {\n                    if (j == 0) {\n                        t[j] = Integer.MAX_VALUE;\n                    } else {\n                        t[j] = Math.min(t[j-1], grid.get(i).get(j-1));\n                    }\n                } else {\n                    if (j == 0) {\n                        t[j] = Math.min(t[j], grid.get(i-1).get(j));\n                    } else {\n                        t[j] = Math.min(Math.min(t[j], grid.get(i-1).get(j)), Math.min(t[j-1], grid.get(i).get(j-1)));\n                    }\n                }\n                res = Math.max(res, grid.get(i).get(j) - t[j]);\n            }\n        }\n        return res;\n    }\n}\n```
['Java']