（1）題目

來(lái)源

OpenJudge - 1768:最大子矩陣

題目描述

已知矩陣的大小定義為矩陣中所有元素的和。給定一個(gè)矩陣，你的任務(wù)是找到最大的非空(大小至少是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

?這個(gè)子矩陣的大小是15。

輸入格式

輸入是一個(gè)N * N的矩陣。輸入的第一行給出N (0 < N <= 100)。再后面的若干行中，依次（首先從左到右給出第一行的N個(gè)整數(shù)，再?gòu)淖蟮接医o出第二行的N個(gè)整數(shù)……）給出矩陣中的N2個(gè)整數(shù)，整數(shù)之間由空白字符分隔（空格或者空行）。已知矩陣中整數(shù)的范圍都在[-127, 127]。

輸出格式

輸出最大子矩陣的大小。

輸入樣例

?4

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

輸出樣例

15

（2）思路

1. 分析問(wèn)題：分析已知和未知

這道題和最大子段和有所相同，但變成二維的了，推薦看這道題題解的小伙伴們先去看一下我的另一篇題解——最大子段和

最大子段和（洛谷--P1115）-CSDN博客

我們將進(jìn)行以下幾步：a. 枚舉；b. 前綴和。

進(jìn)入分析環(huán)節(jié)

a. 枚舉

你以為我們會(huì)枚舉四個(gè)頂點(diǎn)或一個(gè)頂點(diǎn)和矩陣長(zhǎng)寬或左上頂點(diǎn)和右下頂點(diǎn)嗎？

錯(cuò)?。?！你想想那要寫(xiě)多少層循環(huán)?。?！

如果真那么寫(xiě)，會(huì)是這樣(從舉的例子中可見(jiàn)，枚舉左上頂點(diǎn)和右下頂點(diǎn)的時(shí)間復(fù)雜度應(yīng)該少一點(diǎn)，那就枚舉左上頂點(diǎn)和右下頂點(diǎn)得到所有子矩陣，求和再比較)

#include<iostream>
using namespace std;
int main()
{
	int n,a[105][105],maxi=-130;//矩陣中整數(shù)的范圍都在[-127, 127],maxi=-130
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cin>>a[i][j]; //熟人 
	} 
	for(int x1=1;x1<=n;x1++)
	{
		for(int y1=1;y1<=n;y1++)//枚舉左上頂點(diǎn) 
		{
			for(int x2=x1;x2<=n;x2++)
			{
				for(int y2=y1;y2<=n;y2++)//枚舉右下頂點(diǎn) 
				{
					int sum=0;
					for(int i=x1;i<=x2;i++)
					{
						for(int j=y1;j<=y2;j++) sum+=a[i][j];//求和 
					}
					maxi=max(sum,maxi);//比較，求最大值 
				}
			}
		}
	}
	cout<<maxi; 
	return 0;
}

?你說(shuō)這超不超時(shí)。

看來(lái)，只枚舉是不行了

b. 前綴和

根據(jù)最大子段和的思路，我們可以先求出第一行第一列到剩下每個(gè)位置的子矩陣的和，再通過(guò)拼圖的思路求和

for(int i=1;i<=n;i++)

{

? ? ? ? for(int j=1;j<=n;j++)//枚舉各個(gè)位置

? ? ? ? {

? ? ? ? ? ? ? ? for(int m=1;m<=i;m++)//枚舉第一行第一列到此位置的子矩陣

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? ? ? ? for(int n=1;n<=j;n++) f[i][j]+=a[x][y];//求前綴和

? ? ? ? ? ? ? ? }
? ? ? ? }
}//求前綴和

拼圖的思路作圖如下

假如，若要求紅框內(nèi)矩陣的和，要用(1，1)到紅框內(nèi)矩陣的右下角的矩陣的和(藍(lán)框)，減去剩下的部分，可以先減去橙框和綠框，再把橙框和綠框重疊的部分加回來(lái)(因?yàn)樗粶p了2次)，就可以得到紅框內(nèi)矩陣的和了

修改內(nèi)容：

有沒(méi)有覺(jué)得4重循環(huán)還是多了？

前綴和的內(nèi)容還可以簡(jiǎn)化哦！

但簡(jiǎn)化后的內(nèi)容也要運(yùn)用拼圖思路

如圖所示

?如果要求紅框矩陣內(nèi)的和，可以用（黃框+綠框-重疊部分+藍(lán)圈=紅框）的公式求和。

可以這樣做的原因是，黃框和綠框以及重疊部分已經(jīng)求過(guò)了！?。≡偌由?span style="color:#4da8ee;">藍(lán)圈(a[i])就可以了。

具體代碼如下

for(int i=1;i<=n;i++)

{

????????for(int j=1;j<=n;j++)

????????{

????????????????f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];//拼圖思路
??????? }
}

2. 數(shù)據(jù)定義：已知和未知的取名和類型

n：輸入是一個(gè)N * N的矩陣

a[105][105]：輸入的矩陣，0 < n <= 100

f[105][105]：第一行第一列到剩下每個(gè)位置的子矩陣的和，0 < n <= 100

sum：所有子矩陣的和

maxi：所有子矩陣中最大和，矩陣中整數(shù)的范圍都在[-127, 127]

3. 數(shù)據(jù)輸入：輸入已知?

cin>>n;

for(int i=1;i<=n;i++)

{

? ? ? ? for(int j=1;j<=n;j++) cin>>a[i][j];

}

4. 數(shù)據(jù)計(jì)算：數(shù)字建模+設(shè)計(jì)算法

找前綴和的代碼在前面已經(jīng)給大家講過(guò)了，下面是拼圖的思路

for(int r1=1;r1<=n;r1++)

{

????????for(int c1=1;c1<=n;c1++)//枚舉左上頂點(diǎn)

? ? ? ? {

????????????????for(int r2=r1;r2<=n;r2++)

? ? ? ? ? ? ? ? {

????????????????????????for(int c2=c1;c2<=n;c2++)枚舉右下頂點(diǎn)

? ? ? ? ? ? ? ? ? ? ? ? {

????????????????????????????????sum=f[r2][c2]+f[r1-1][c1-1]-f[r1-1][c2]-f[r2][c1-1];//拼圖求和

????????????????????????????????maxi=max(maxi,sum);//比較

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? sum=0;//清零

? ? ? ? ? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? }
? ? ? ? }
}文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-858894.html

（3）完整AC代碼

#include<iostream>
using namespace std;
int main()
{
	int f1[105][105]={0};
	int n,a[105][105],f[105][105]={0},sum=0,maxi=-0x3f3f3f3f;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) cin>>a[i][j];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
		}
	}
	for(int r1=1;r1<=n;r1++)
	{
		for(int c1=1;c1<=n;c1++)
		{
			for(int r2=r1;r2<=n;r2++)
			{
				for(int c2=c1;c2<=n;c2++)
				{
					sum=f[r2][c2]+f[r1-1][c1-1]-f[r1-1][c2]-f[r2][c1-1];
					maxi=max(maxi,sum);
					sum=0;
				}
			}
		}
	}
	cout<<maxi;
	return 0;
}

到了這里，關(guān)于最大子矩陣（openjudge noi-2.6基本算法之動(dòng)態(tài)規(guī)劃-1768）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！