最大子矩阵

暑假集训 day1 的一道水题

题目描述

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是 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

输入格式:

输入是一个 N×N 的矩阵。输入的第一行给出 N(0<N≤100)。再后面的若干行中,依次(首先从左到右给出第一行的 N 个整数,再从左到右给出第二行的 N 个整数……)给出矩阵中的 N×N 个整数,整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127, 127]

输出格式:

输出最大子矩阵的大小

输入样例:

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

输出样例:

15

解题思路

刚开始的时候想到用暴力进行求解,一共 6 重循环,分别的作用是枚举起点 x 坐标起点 y 坐标终点 x 坐标终点 y 坐标,剩下的 2 重用于计算圈成的区间的和

按照这个思路的话,复杂度差不多达到 O(n^6)

于是,我就想到用前缀和

#include<stdio.h>
#include<algorithm>

int n,a[105][105],f[105][105],ans=0;
int main()
{
	scanf("%d",&n);
	f[0][0]=f[0][1]=f[1][0]=0;//要不要问题不大 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
		}
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int l=i;l<=n;l++)
				for(int m=j;m<=n;m++)
					ans=std::max(ans,f[l][m]-f[l][j-1]-f[i-1][m]+f[i-1][j-1]);
	
	printf("%d\n",ans);
	return 0;
}
图片无法通过博客内部上传,只能使用外部图床

好在这道题数据范围太水了,n 最大不超过 100,因此这样投机取巧完全可以过

其实这道题本应该是用动态规划解决的,动态规划的代码到时候再发吧(懒)