C++中不大於K的矩形最大和

假設我們有一個二維矩陣和一個整數k。我們必須找到矩陣中一個矩形的最大和，使其和不大於k。如果輸入如下：

101
0-32

並且k = 3，則輸出將為3，因為標記矩形的和為3。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式`maxSumSubmatrix()`，它將接收一個二維陣列`matrix`和`k`作為引數。
  • n := 行數，m := 列數
  • ans := -inf
  • for l := 0 to m-1:
  • 定義一個大小為n的陣列`rowSum`
  • for r := l to m-1:
    • for i := 0 to n-1:
      • rowSum[i] := rowSum[i] + matrix[i][r]
    • 定義一個集合s
    • 將0插入s
    • currSum := 0
    • for i := 0 to n-1:
      • currSum := currSum + rowSum[i]
      • it := 集合s中不大於currSum – k的第一個元素
      • if it != s的最後一個元素:
        • ans := max(ans, (currSum - it))
      • 將currSum插入s
  • 返回ans

讓我們看下面的實現來更好地理解：

示例

 線上演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
      int n = matrix.size();
      int m = matrix[0].size();
      int ans = INT_MIN;
      for(int l = 0; l < m; l++){
         vector <int> rowSum(n);
         for(int r = l; r < m; r++){
            for(int i = 0; i < n; i++)rowSum[i] += matrix[i][r];
            set < int > s;
            s.insert(0);
            int currSum = 0;
            for(int i = 0; i < n; i++){
               currSum += rowSum[i];
               set <int> :: iterator it = s.lower_bound(currSum - k);
               if(it != s.end()){
                  ans = max(ans, (currSum - *it));
               }
               s.insert(currSum);
            }
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,0,1},{0,-3,2}};
   cout << (ob.maxSumSubmatrix(v, 3));
}

輸入

[{1,0,1},{0,-3,2}]
3

輸出

3

更新於：2020年6月1日

瀏覽量：108

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告