[C++] DP
Intuition\nFor each element $grid[i][j]$, find the smallest element on the top-left of it.\n\n# Code\n\nclass Solution {\npublic:\n    int maxScore(vector<vecto
# Intuition\nFor each element $grid[i][j]$, find the smallest element on the top-left of it.\n\n# Code\n```\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size(), ans = INT_MIN;\n        vector<int> dp(n, INT_MAX);\n        dp[0] = grid[0][0];\n        for (int j = 1; j < n; j++)\n        {\n            ans = max(ans, grid[0][j] - dp[j - 1]);\n            dp[j] = min(dp[j - 1], grid[0][j]);\n        }\n        for (int i = 1; i < m; i++)\n        {\n            int minr = grid[i][0];\n            ans = max(ans, grid[i][0] - dp[0]);\n            dp[0] = min(dp[0], grid[i][0]);\n            for (int j = 1; j < n; j++)\n            {\n                ans = max(ans, grid[i][j] - min(dp[j], minr));\n                minr = min(minr, grid[i][j]);\n                dp[j] = min(dp[j], minr);\n            }\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C++']