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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: удаление Категория:На проверку)
 
(не показано 12 промежуточных версий 2 участников)
Строка 1: Строка 1:
 +
* https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k
  
    class Solution {
+
<code-cpp>
 +
class Solution {
 
     public:   
 
     public:   
 
     int maxSumSubmatrix(vector<vector<int>> &matrix, int k) {
 
     int maxSumSubmatrix(vector<vector<int>> &matrix, int k) {
Строка 10: Строка 12:
 
       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;
}};
+
        }};
 
+
</code-cpp>
[[Категория:На проверку]]
+

Текущая версия на 16:16, 25 мая 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;
        }};