A48215. 最大子矩阵已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。比如，如下4 * 4的矩阵0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2的最大子矩阵是9 2-4 1-1 8这个子矩阵的大小是15。
填空题
较难
知识点
题目描述
最大子矩阵
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
比如，如下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。
参考答案
#include<bits/stdc++.h>
using namespace std;
int s(int b[],int N)
{
int c=0,max=0,i;
for(i=1;i<=N;i++)
{if(c>0)
c+=b[i];
else c=b[i];
if(max<c)
max=c;}
return max;
}
int main()
{ //freopen("d://data.in","r",stdin);
int a[105][105],b[105];
int N,n=1,i,j,k,sum,max=0;
cin>>N;
for(i=1;i<=N;i++)
{
for(j=1;j<=N;j++)
cin>>a[i][j];}
while(n<=N)
{for(j=1;j<=N;j++)
b[j]=0;
for(j=n;j<=N;j++)
{
for(k=1;k<=N;k++)
b[k]+=a[j][k];
sum=s(b,N);
if(max<sum)
max=sum;
}
n++;}
cout<<max<<endl;
return 0;
}答案解析
将矩阵的每一列压缩成一行，对压缩成的一行求最大子序列，利用循环求每行开始压缩后所得的最大子序列的值，最终得到的最大值则为最大子矩阵的值。
上一题
下一题