本文主要是介绍1224：最大子矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1224：最大子矩阵
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1×11×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。
【输入】
输入是一个N×N的矩阵。输入的第一行给出N(0<N≤100)。再后面的若干行中，依次(首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127]。
【输出】
输出最大子矩阵的大小。
题解分析：网上看了几个题解，不是太清晰，自己写一个吧
使用方法是连续子序列之和等于两个前缀和之差的方法，将其用于二维矩阵的话也是可以的。
首先对列求连续和，再此基础上对行求连续和，这样得到新矩阵i，j保存的是（1,1）（i，j）确定的矩阵和。
放图吧。
#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
using namespace std;
//最大连续和问题，枚举法的话n平方取2个构成矩形，然后对矩形进行累加，复杂度可能达到n的6次方
//但不枚举是不行的，所以算法应该对矩阵求和进行优化
const int maxn=105;
int a[maxn][maxn],m[maxn][maxn],n;int main()
{int i,j,k,l,sum,maxa;cin>>n;memset(a,0,sizeof(a));memset(m,0,sizeof(m));for(i=1; i<=n; i++){for(j=1; j<=n; j++){cin>>a[i][j];m[i][j]=a[i][j];}}//先求出列的累加和,也保存在a里面for(j=1; j<=n; j++){sum=a[1][j];for(i=2; i<=n; i++){sum+=a[i][j];a[i][j]=sum;}}//求出行的累加和，这样a[i][j]存储的就是以1，1位顶点和以i，j位顶点的矩阵和for(i=1; i<=n; i++){sum=a[i][1];for(j=2; j<=n; j++){sum+=a[i][j];a[i][j]=sum;}}for(i=1; i<=n; i++)//对每一个i，j都要从1，1探索矩阵中每个点，从而获取其最大值{for(j=1; j<=n; j++){for(k=1; k<=i; k++) //左上角k，l和右下角i，j组成的矩形和{for(l=1; l<=j; l++){int temp=a[i][j];temp=temp-a[k-1][j]-a[i][l-1]+a[k-1][l-1]; //k-1,l-1不会越界，因为数组边缘都是0.if(temp>m[i][j])m[i][j]=temp;}}}}maxa=m[1][1];for(i=1; i<=n; i++){for(j=1; j<=n; j++){if(m[i][j]>maxa)maxa=m[i][j];}}cout<<maxa;return 0;
}这篇关于1224：最大子矩阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
