Участник:Михеева Анастасия Максимовна/Max Sum of Rectangle No Larger Than K — различия между версиями
Материал из DISCOPAL
| Строка 1: | Строка 1: | ||
| − | class Solution { | + | |
| + | class Solution { | ||
public: | public: | ||
int maxSumSubmatrix(vector<vector<int>> &matrix, int k) { | int maxSumSubmatrix(vector<vector<int>> &matrix, int k) { | ||
| Строка 24: | Строка 25: | ||
} | } | ||
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; }};