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

力扣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;}};