题目大意
众所周知，矩阵的大小定义为矩阵中所有元素的总和。给定一个矩阵，您的任务是找到最大的非空矩阵（至少在大小上）。
1
*
1
1*1
1*1) 子矩阵。
例如，它看起来像这样：
四
*
四
4*4
4*4子矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩阵是
9 2
-4 1
-1 8
该子矩阵的大小为
15
15
15.
输入格式
进入
氮
*
氮
N*N
N*N
（
1
=
氮
=
500
）
(1=N=500)
(1=N=500) 整数矩阵。每个数字的范围如下：
–
127
-127
127
127
127
127 之间。
输出格式
打印最大子矩阵的大小。
输入样本
四
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
输出样本
15
基本思路
暴力枚举肯定是我们的第一个想法，但即使有二维前缀和优化，它仍然
（
n
四
）
O(n^4)
O(n4)，这显然是无法容忍的。观察数据大小，我们可以看到以下内容：
（
n
3
）
O(n^3)
由于不同的原因，O(n3) 是可以承受的。
F
啊
r
为了
for 循环的情况并非总是如此。
n
n
n ，那么我们如何优化它呢？
首先，我们可以枚举子矩阵的宽度，即子矩阵的列数。然后将该子矩阵的每一行中的数字相加成一个数字。
此时你应该有一个像这样的图表：
n
n
n 个数字的序列（因为我们只枚举了宽度和长度，即行数，所以默认为
n
n
n).下一步是确定行数。问题转化为：
n
n
选择n个数之和最大的连续子序列。 在这张照片中是
11
,
–
3
,
7
11, -3, 7
11,3,7，确定的子矩阵为：
{
9
,
2
}
\\{9,2\\}
{9,2}
{
–
四
,
1
}
\\{-4,1\\}
{4,1}
{
–
1
,
8
}
\\{-1,8\\}
{1,8}。
由于负值，还有另一个问题需要注意。
是
n
s
回答
ans 必须指定最小值。
核心代码
#includebits/stdc++.h
使用命名空间标准。
typedef 长长ll；
常量整数N=510；
int n,s[N][N],ans=-1e9;
int main(){
ios:sync_with_stdio(假);
胫。
for(int i=1;i=n;i++)
for(int j=1;j=n;j++){
cins[i][j]；
s[i][j]+=s[i][j-1]；
}
for(int d=0;dn;d++){//枚举宽度
for(int i=1;i+d=n;i++){
int j=i+d,tmp=0;
for(int k=1;k=n;k++){
tmp+=(s[k][j]-s[k][i-1]); //将此行中的数字视为数字。
ans=max(ans,tmp);
tmp=max(tmp,0);
}
}
}
库坦人。
//2
//-4 -2
//-3 -1
//
//-1
返回0。
}
#[SSL 1056]以上Maximum Submatrix相关内容来源网络，仅供参考。相关信息请参见官方公告。
原创文章，作者：CSDN，如若转载，请注明出处：https://www.sudun.com/ask/93003.html
