Участник:Михеева Анастасия Максимовна/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) {
int row = matrix.size();
+
    int row = matrix.size();
if (row == 0)
+
    if (row == 0)
return 0;
+
return 0;
int col = matrix[0].size();
+
    int col = matrix[0].size();
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);
+
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);

Версия 20:06, 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; }};