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

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;
	}};

[[Категория:На проверку]]