363. 矩形区域不超过 K 的最大数值和

（下面是理论的分析，但是这次实在是不想搞了。感觉现在的代码是左开右闭，但是好像并不是，因为这个区间的问题，需要在set中加一个0。）

这个$S_l$和$S_r$当作一维时表示的是(0,l]，这个左开右闭很有讲究，这样当$S_r-S_l$恰好表示[l,r]。

2. 题目

给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/max-sum-of-rectangle-no-larger-than-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

3. 答案

class Solution {
public:
int maxSumSubmatrix(const vector>& matrix, int k) {
	int row = matrix.size(), col=matrix[0].size();
	vector>dp(row,vector(col,0));
	for(int i=0;i=0?dp[i-1][j]:0;
			auto num2 = j-1>=0?dp[i][j-1]:0;
			auto num3 = i-1>=0&&j-1>=0?dp[i-1][j-1]:0;
			dp[i][j] = num1+num2-num3+matrix[i][j];
		}
	}
	int ret = INT_MIN;
	for(int up=0;upmin_sum;//<这个参数是sl或sr，就是从左到右的，而不是某一列的
			min_sum.insert(0);
			for(int r=0;r=0?dp[up-1][r]:0;
				int sr = dp[down][r] - num;
				auto it_sl=min_sum.lower_bound(sr-k);
				if(it_sl!=min_sum.end())
				{
					ret = max(ret, sr-*it_sl);
				}
				min_sum.insert(sr);
			}
		}
	}
	return ret;
}

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39