C++前缀和算法应用：矩形区域不超过 K 的最大数值和

class Solution {
public:
int maxSumSubmatrix(vector<vector>& matrix, int k) {
m_r = matrix.size();
m_c = matrix.front().size();
vector<vector> vPreSum(m_r+1,vector(m_c+1,0)); //vPreSum[r][c] 以(0,0)开始，宽高为c r的矩形
for (int r = 1; r <= m_r; r++)
{
for (int c = 1; c <= m_c; c++)
{
//令r=1,c=1 vPreSum[1][1] = 0 +0 + matrix[0][0] -0
//令r=2,c=2 vPreSum[2][2] = vPreSum[1][2] +vPreSum[2][1] + matrix[1][1] + vPreSum[1][1]
vPreSum[r][c] = vPreSum[r - 1][c] + vPreSum[r][c - 1] + matrix[r - 1][c - 1] - vPreSum[r - 1][c - 1];
}
}
int iMin = INT_MIN;
//vector<vector> vDebug(m_r, vector(m_c,INT_MIN));
for (int left = 0; left < m_c ; left++ )
{
for (int right = left ; right < m_c; right++ )
{
//row和right 是右下角的坐标
set setSum = { 0 };
for (int row = 0; row < m_r; row++)
{
const int iLeftRight = vPreSum[row + 1][right + 1]
• vPreSum[row + 1][left];
//iLeftRight - x <=k ==> -x <= k - iLeftRight ==> x >= iLeftRight-k
auto it = setSum.lower_bound(iLeftRight - k);
if (setSum.end() != it)
{
iMin = max(iMin, iLeftRight - *it);
//vDebug[row][right] = iLeftRight - *it;
}
setSum.emplace(iLeftRight);
}
}
}
return iMin;
}
int m_r, m_c;
};

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
vector<vector> matrix = { {1, 2, 3}, { 4,5,6 } };
int k = 2;
auto res = Solution().maxSumSubmatrix(matrix, k);
Assert(res, 2);
matrix = { {1, 0, 1}, { 0,-2,3 } };
k = 2;
res = Solution().maxSumSubmatrix(matrix, k);
Assert(res, 2);
matrix = { {2,2,-1} };
k = 3;
res = Solution().maxSumSubmatrix(matrix, k);
Assert(res, 3);
CConsole::Out(res);
}