Участник:Михеева Анастасия Максимовна/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); | |
| − | + | 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); | 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; }};