力扣3148.矩阵中的最大得分

• 类似二维前缀和

  • 枚举右下角 求(i,j) - (0,0)的子矩阵的最小值
  • 每次与当前点作差 求答案

•   class Solution {
    public:
        int maxScore(vector<vector<int>>& grid) {
            int res = INT_MIN;
            int m = grid.size(),n = grid[0].size();
            vector<vector<int>> s(m+1,vector<int>(n+1,INT_MAX));
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
                {
                    int t = min(s[i][j+1],s[i+1][j]);
                    res = max(res,grid[i][j] - t);
                    s[i+1][j+1] = min(t,grid[i][j]);
                }
            return res;
        }
    };