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

## 基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例

## 题目

m == matrix.length

n == matrix[i].length

1 <= m, n <= 100

-100 <= matrix[i][j] <= 100

-105 <= k <= 105

## 分析

### 二维前缀和

vPreSum[r][c] 记录以(0,0)开始，宽高为c r的矩形和。vPreSum[r][c] = vPreSum[r - 1][c] + vPreSum[r][c - 1] + matrix[r - 1][c - 1] - vPreSum[r - 1][c - 1];

 vPreSum[r - 1][c] 绿色实心矩形的和 vPreSum[r][c - 1] 蓝色空心矩形 matrix[r - 1][c - 1] 黄色矩形 vPreSum[r - 1][c - 1] 蓝绿重叠部分

## 源码

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

## 扩展阅读

#### 视频课程

https://edu.csdn.net/course/detail/38771

https://edu.csdn.net/lecturer/6176

#### 相关下载

 鄙人想对大家说的话 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 墨家名称的来源：有所得以墨记之。 如果程序是一条龙，那算法就是他的是睛

#### 测试环境

|
13天前
|

32 8
|
14天前
|

30 9
|
11天前
|

C++ 补充之常用排序算法
C++ 补充之常用排序算法
14 1
|
11天前
|

C++ 补充之常用查找算法
C++ 补充之常用查找算法
14 1
|
11天前
|

C++ 补充之常用遍历算法
C++ 补充之常用遍历算法
13 1
|
5天前
|

|
11天前
|

C++ 补充之常用拷贝和替换算法
C++ 补充之常用拷贝和替换算法
7 0
|
11天前
|

KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用
16 0
|
2天前
|

MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现
7 1
|
9天前
|

Matlab|基于改进鲸鱼优化算法的微网系统能量优化管理matlab-源码

25 2