- 363. 矩形区域不超过 K 的最大数值和
- 题干
- 声明
- 方法1-暴力枚举+简单dp
- 方法2-暴力枚举+二维数组前缀和
- 方法3-固定边界搜索
- 方法4-固定边界搜索+dp优化
- 方法5-固定边界搜索+前缀和+二分查找
题干本题涉及内容：一/二维前缀和问题、降维问题、暴力枚举问题、dp问题、二分查找问题
给你一个 m ∗ n m * n m∗n 的矩阵 m a t r i x matrix matrix 和一个整数 k k k ，找出并返回矩阵内部矩形区域的不超过 k k k 的最大数值和。
题目数据保证总会存在一个数值和不超过 k k k 的矩形区域。
示例1：
输入：matrix = [[1,0,1],[0,-2,3]], k = 2 输出：2 解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
数据范围
- 1 ≤ R o w S i z e , C o l S i z e ≤ 100 1le RowSize,ColSizele 100 1≤RowSize,ColSize≤100
- 1 ≤ m a t r i x [ i ] [ j ] ≤ 100 1le matrix[i][j]le 100 1≤matrix[i][j]≤100
- − 1 0 5 ≤ k ≤ 1 0 5 -10^5le kle 10^5 −105≤k≤105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法1-暴力枚举+简单dp下方代码默认数据已经读入在matrix二维数组，然后主函数调用Max_Sum_Sub_Matrix这个子函数返回result
时间复杂度，dp时间复杂度为指数级增长，并且Max_Sum_Sub_Matrix循环复杂度为 O ( n 4 ) O(n^4) O(n4)，两者相乘，嘶~
都不敢上交到leetcode
#define Max(a,b) (a)>(b)?(a):(b)
//首先展示的是最为暴力的解法
#define inf 1000000
int dp(int **matrix,int r1,int c1,int r2,int c2){//表示对区域求和
if(r1>r2||c1>c2)return 0;
else if(r1==r2&&c1==c2)return matrix[r1][c1];
else return dp(matrix,r1,c1,r2-1,c2)+dp(matrix,r1,c1,r2,c2-1)+matrix[r2][c2];
}
int Max_Sum_Sub_Matrix(int **matrix,int RowSize,int ColSize,int k){
//直接利用dp求解
int r1,c1,r2,c2;
int max=-inf;
for(r1=0;r1
方法2-暴力枚举+二维数组前缀和
使用前缀和优化后，时间复杂度降至
O
(
n
4
)
O(n^4)
O(n4),(前缀和的优势是降低了计算区域和的时间)
#define Max(a,b) (a)>(b)?(a):(b)
#define inf 1000000
int Max_Sum_Sub_Matrix(int **matrix,int RowSize,int ColSize,int k){
int r1,c1,r2,c2;
int i,j;
int max=-inf;
int **prefix=(int**)calloc(sizeof(int*),RowSize+1);
for(int i=0;i<=RowSize;i++)
prefix[i]=(int*)calloc(sizeof(int),ColSize+1);
for(i=1;i<=RowSize;i++){
for(j=1;j<=ColSize;j++)//prefix[i][j]相对于matrix要移出来一格
prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+matrix[i-1][j-1];
}//prefix[i][j]表示
for(r1=0;r1
方法3-固定边界搜索
具体思路有
a
+
b
+
c
=
k
a+b+c=k
a+b+c=k启发而来，要在一个数组中查找三个和为k的数是否存在，最快的办法就是固定两个数，将数组排序，再在其中二分查找第三个数
所耗费的时间大概为上一种方法的1/3（但是其实不知道为啥会提升那么多）
目前这种方法在c提交中大概击败了95%左右
int Max_Sum_Sub_Matrix(int **matrix,int RowSize,int ColSize,int K){
int *data=(int*)calloc(sizeof(int),ColSize+2);
// int data[inf]={0};
int i,j,k,best;//best代表不大于k的最优和
data[0]=0;
best=-inf;
for(i=0;iK)continue;
else return K;
}
}
}
memset(data,0,sizeof(int)*(ColSize+2));
}
return best;
}
方法4-固定边界搜索+dp优化
思路是先利用动态规划求出i-j行的最大子数组，根据最大子数组的dp值，判断是否要进行继续的查找，如果小于k，那么直接更新best的值，再继续更换行数就行查找，如果等于k，直接返回k，如果大于k，此时无法确定best的值，需要执行上面的边界搜索
可以将几乎一半的方案优化到
O
(
n
3
)
O(n^3)
O(n3)
效果显著
int Max_Sum_Sub_Matrix(int **matrix,int RowSize,int ColSize,int K){
int *data=(int*)calloc(sizeof(int),ColSize+2);
// int data[inf]={0};
int i,j,k,best;//best代表不大于k的最优和
data[0]=0;
best=-inf;
for(i=0;iK)continue;
else return K;
}
}
}
memset(data,0,sizeof(int)*(ColSize+2));
}
return best;
}
方法5-固定边界搜索+前缀和+二分查找
该方法对c而言，仅适用于数组元素均正的情况，但是java等由于其数据结构的原因，可以通过维护一个有序集合来适用所有情况
仅说一下具体的思路，代码暂不提供
- 现在对于第
i
−
j
i-j
i−j行，已经计算出了前缀和
p
r
e
f
i
x
prefix
prefix数组，
p
r
e
f
i
x
[
l
]
prefix[l]
prefix[l]表示的是前l项的前缀和，此时要查找一个区域和不大于
K
K
K的最大值
- 自然想到，该条件等价于寻找
p
r
e
f
i
x
[
l
]
+
K
<
=
p
r
e
f
i
x
[
r
]
prefix[l]+K<=prefix[r]
prefix[l]+K<=prefix[r]（l,r代表的left和right，左右边界）
- 第一种思路，对l进行遍历，在prefix[l~ColSize]范围内二分查找
p
r
e
f
i
x
[
i
]
+
K
prefix[i]+K
prefix[i]+K的右边界-1即可（思考一下为啥要选择查找右边界呢？）
- 第二种思路，条件转化为
p
r
e
f
i
x
[
i
]
<
=
p
r
e
f
i
x
[
r
]
−
K
prefix[i]<=prefix[r]-K
prefix[i]<=prefix[r]−K,对r进行遍历，在prefix[l~r]范围内二分查找
p
r
e
f
i
x
[
r
]
−
K
prefix[r]-K
prefix[r]−K的左边界+1即可
- 但是上述的两种思路均是在KaTeX parse error: Undefined control sequence: and at position 18: …trix[i][j]ge 0̲a̲n̲d̲ ̲K ge 0的情况下适用，本题中存在小于0的数组值
- 此时需要选择第二种思路，手动维护一个有序数组，java中可以适用set集合
O
(
1
)
O(1)
O(1)实现，但是c中没有这种数据结构所以手动维护的时间甚至要大于查找时间，所以暂时放弃实现
时间复杂度为
O
(
n
3
l
o
g
n
)
O(n^3logn)
O(n3logn)
