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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 14: Строка 14:
 
             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:36, 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; }};