第363题---Max Sum of Rectangle No Larger Than K

• 题意描述
  • 给定一个二维数组，求长方形的和不超过k的最大的数
    
    
• 思路：
  • 先转化为一维数组，然后动态规划
    
    
• 代码

  class Solution {
  public:
      int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
          if (matrix.empty()) return 0;
          int row = matrix.size(), col = matrix[0].size(), res = INT_MIN;
          for (int l = 0; l < col; ++l) {
              vector<int> sums(row, 0);
              for (int r = l; r < col; ++r) {
                  for (int i = 0; i < row; ++i) {
                      sums[i] += matrix[i][r];
                  }
              
                  // Find the max subarray no more than K 
                  set<int> accuSet;
                  accuSet.insert(0);
                  int curSum = 0, curMax = INT_MIN;
                  for (int sum : sums) {
                      curSum += sum;
                      set<int>::iterator it = accuSet.lower_bound(curSum - k);
                      if (it != accuSet.end()) curMax = std::max(curMax, curSum - *it);
                      accuSet.insert(curSum);
                  }
                  res = std::max(res, curMax);
              }
          }
          return res;
      }
  };