Участник:Михеева Анастасия Максимовна/Max Sum of Rectangle No Larger Than K

Материал из DISCOPAL
< Участник:Михеева Анастасия Максимовна
Версия от 20:00, 23 мая 2020; Михеева Анастасия Максимовна (обсуждение | вклад) (Новая страница: « class Solution { public: int maxSumSubmatrix(vector<vector<int>> &matrix, int k) { int row = matrix.size(); if (row == 0) return 0; int co…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
   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; }};