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

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

Версия 20:09, 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; }};