【蓝桥杯】最大子阵

题目

给定一个 <math> <semantics> <mrow> <mi> n </mi> <mo> × </mo> <mi> m </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> n \times m </annotation> </semantics> </math>n×m 的矩阵 <math> <semantics> <mrow> <mi> A </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> A </annotation> </semantics> </math>A，求 <math> <semantics> <mrow> <mi> A </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> A </annotation> </semantics> </math>A 中的一个非空子矩阵，使这个子矩阵中的元素和最大。

其中， <math> <semantics> <mrow> <mi> A </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> A </annotation> </semantics> </math>A 的子矩阵指在 <math> <semantics> <mrow> <mi> A </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> A </annotation> </semantics> </math>A 中行和列均连续的一部分。

输入格式

输入的第一行包含两个整数 <math> <semantics> <mrow> <mi> n </mi> <mo separator="true"> , </mo> <mi> m </mi> <mo> ( </mo> <mn> 1 </mn> <mo> ≤ </mo> <mi> n </mi> <mo separator="true"> , </mo> <mi> m </mi> <mo> ≤ </mo> <mn> 50 </mn> <mo> ) </mo> </mrow> <annotation encoding="application&#47;x&#45;tex"> n,m(1 \leq n,m \leq 50) </annotation> </semantics> </math>n,m(1≤n,m≤50)，分别表示矩阵 <math> <semantics> <mrow> <mi> A </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> A </annotation> </semantics> </math>A 的行数和列数。

接下来 <math> <semantics> <mrow> <mi> n </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> n </annotation> </semantics> </math>n 行，每行 <math> <semantics> <mrow> <mi> m </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> m </annotation> </semantics> </math>m 个整数，表示矩阵 <math> <semantics> <mrow> <msub> <mi> A </mi> <mrow> <mi> i </mi> <mo separator="true"> , </mo> <mi> j </mi> </mrow> </msub> <mo> ( </mo> <mo> − </mo> <mn> 1000 </mn> <mo> ≤ </mo> <msub> <mi> A </mi> <mrow> <mi> i </mi> <mo separator="true"> , </mo> <mi> j </mi> </mrow> </msub> <mo> ≤ </mo> <mn> 1000 </mn> <mo> ) </mo> </mrow> <annotation encoding="application&#47;x&#45;tex"> A_{i,j}(-1000 \leq A_{i,j} \leq 1000) </annotation> </semantics> </math>Ai,j​(−1000≤Ai,j​≤1000)。

输出格式

输出一行，包含一个整数，表示 <math> <semantics> <mrow> <mi> A </mi> </mrow> <annotation encoding="application&#47;x&#45;tex"> A </annotation> </semantics> </math>A 中最大子矩阵的元素和。

样例输入

3 3

2 -4 1

-1 2 1

4 -2 2

样例输出

6

题解

很自然的想到当遍历到某个点，从该点出发，横向，纵向找到全部子矩阵，对比大小

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 50+5;
int Max = -99999999;
int n,m;
int a[N][N];
void FindMax(int row,int line){
	for(int i=row;i<n;i++) // 限制子矩阵横行长度
		for(int j=line;j<m;j++){  // 限制子矩阵纵向长度
			int sum = 0;
			// 求子矩阵总和
			for(int w=row;w<=i;w++)  
				for(int k=line;k<=j;k++)
					sum +=a[w][k];
			Max = max(sum,Max);
		}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>a[i][j];
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			FindMax(i,j);
	cout<<Max;
	return 0;
}

返回目录，查看更多