Участник:Михеева Анастасия Максимовна/Max Sum of Rectangle No Larger Than K — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
+
   
 
     class Solution {
 
     class Solution {
 
     public:   
 
     public:   
Строка 10: Строка 10:
 
       for (int l = 0; l < col; l++) {
 
       for (int l = 0; l < col; l++) {
 
           vector<int> sums(row, 0);
 
           vector<int> sums(row, 0);
  for (int r = l; r < col; r++) {
+
for (int r = l; r < col; r++) {
    for (int i = 0; i < row; i++)
+
for (int i = 0; i < row; i++)
        sums[i] += matrix[i][r];
+
sums[i] += matrix[i][r];
        set<int> sumSet;
+
set<int> sumSet;
 
                 sumSet.insert(0);
 
                 sumSet.insert(0);
int curSum = 0;
+
int curSum = 0;
int curMax = INT_MIN;
+
int curMax = INT_MIN;
for (auto sum : sums) {
+
for (auto sum : sums) {
  curSum += sum;
+
curSum += sum;
  auto it = sumSet.lower_bound(curSum - k);
+
auto it = sumSet.lower_bound(curSum — k);
          if (it != sumSet.end())
+
if (it != sumSet.end())
    curMax = max(curMax, curSum - *it);
+
curMax = max(curMax, curSum — *it);
    sumSet.insert(curSum);
+
sumSet.insert(curSum);
  }
+
}
  ret = max(ret, curMax);
+
ret = max(ret, curMax);
  }
+
}
}
+
}
 
return ret;
 
return ret;
 
}};
 
}};
  
 
[[Категория:На проверку]]
 
[[Категория:На проверку]]

Версия 20:26, 23 мая 2020

   class Solution {
   public:   
   int maxSumSubmatrix(vector<vector<int>> &matrix, int k) {
      int row = matrix.size();
      if (row == 0)
          return 0;
      int col = matrix[0].size();
      int ret = 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]; set<int> sumSet;

               sumSet.insert(0);

int curSum = 0; int curMax = INT_MIN; for (auto sum : sums) { curSum += sum; auto it = sumSet.lower_bound(curSum — k); if (it != sumSet.end()) curMax = max(curMax, curSum — *it); sumSet.insert(curSum); } ret = max(ret, curMax); } } return ret; }};